732. My Calendar III

My Calendar III

Problem Description

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.)

You are given some events [start, end), after each given event, return an integer k representing the maximum k-booking between all the previous events.

Implement the MyCalendarThree class:

• MyCalendarThree() Initializes the object.
• int book(int start, int end) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

 

Example 1:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

Explanation
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // return 1, The first event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarThree.book(50, 60); // return 1, The second event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarThree.book(10, 40); // return 2, The third event [10, 40) intersects the first event, and the maximum k-booking is a 2-booking.
myCalendarThree.book(5, 15); // return 3, The remaining events cause the maximum K-booking to be only a 3-booking.
myCalendarThree.book(5, 10); // return 3
myCalendarThree.book(25, 55); // return 3

 

Constraints:

• 0 <= start < end <= 109
• At most 400 calls will be made to book.

This is a classic scheduling problem, where we want to see when two or more times overlap.

How do we know if two times overlap? We know when at any point in time we have two or more START times.

An event starts, and it ends. If an event starts, and another one starts before that first one ends, we have an overlap.

Code:

const START = 1;
const END = -1;

var MyCalendarThree = function () {
    this.kbookings = 0;
    this.schedule = [];
};

MyCalendarThree.prototype.book = function (start, end) {
    // push to shedule
    // denote start with 1 at index 1, and end with -1 at index 1
    this.schedule.push([start, START], [end, END]);

    // sort O(n log n)
    this.schedule.sort(([t1, s1], [t2, s2]) => {
        if (t1 === t2) {
            // Times are the same, so we put endings first in our list
            return s1 - s2;
        }
        // sort by ascending time
        return t1 - t2;
    });
	
	// Sort can be condensed down to this
	// this.schedule.sort(([t1, s1], [t2, s2]) => (t1 === t2 ? s1 - s2 : t1 - t2));

    let count = 0;

    // O(schdule.length)
    for (let i = 0; i <= this.schedule.length - 1; i++) {
        let [_, space] = this.schedule[i];
        // If
        if (space === START) {
            count++;
            // Did we find a new max booking?
            this.kbookings = Math.max(this.kbookings, count);
        } else {
            count--;
        }
    }

    return this.kbookings;
};

Approach) Map + Sortlist

class SortList {
    constructor() {
        this.list = [];
    }

    add(time) {
        let l = 0;
        let r = this.list.length - 1;

        while(l <= r) {
            const m = l + ((r - l) >>> 1);
            if(time <= this.list[m]) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        this.list.splice(l, 0, time);
    }

    checkIsAlreadyInList(time) {
        let l = 0;
        let r = this.list.length - 1;

        while(l <= r) {
            const m = l + ((r - l) >>> 1);
            if(time === this.list[m]) return true;
            if(time < this.list[m]) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        return false;
    }
}

var MyCalendarThree = function() {
    this.map = new Map();
    this.sl = new SortList();
    this.addToMap = (time) => !this.map.has(time) && this.map.set(time, 0);
    this.saveTime = (time) => !this.sl.checkIsAlreadyInList(time) && this.sl.add(time);
    this.startEvent = (time) => this.map.set(time, this.map.get(time) + 1);
    this.endEvent = (time) => this.map.set(time, this.map.get(time) - 1);
    this.getTimes = () => this.sl.list;
};

MyCalendarThree.prototype.book = function(start, end) {
    this.addToMap(start);
    this.startEvent(start);

    this.addToMap(end);
    this.endEvent(end);

    this.saveTime(start);
    this.saveTime(end);
    const times = this.getTimes();

    let max = 0;
    let curr = 0;
    for(const time of times) {
        curr += this.map.get(time);
        max = Math.max(max, curr);
    }

    return max;
};

Complexity 

Time Complexity

Time complexity will be O(n * (n + log(n) + n )) --> O(n ^ 2).

Space Complexity
space complexity should also be O(n).

Approach) Map + Brute Force (Beginner friendly)

var MyCalendarThree = function() {
    this.tm = {}
};

MyCalendarThree.prototype.book = function(start, end) {
    this.tm[start] = (this.tm[start] || 0) + 1
    this.tm[end] = (this.tm[end] || 0) - 1
    let max = count = 0
    for(let val in this.tm){
        max = Math.max(max, count += this.tm[val])
    }
    return max
};

Approach) Segment Tree

var MyCalendarThree = function() {
    this.st = new SegmentTree(0, Math.pow(10,9));
};

MyCalendarThree.prototype.book = function(start, end) {
    this.st.add(start, end);    
    return this.st.getMax();
};

class SegmentTree {
    constructor(start, end) {
        this.root = new TreeNode(start, end);
    }
    
    add(qs, qe, node=this.root) {
        
        // completely outside of query range
        if(qs > node.end || qe <= node.start) {
            return node.val;
        }
        
        // completely covered by query range
        if(qs <= node.start && qe > node.end) {
            node.booked += 1;
            node.val += 1;
            return node.val;
        }

        let mid = (node.start + node.end)/2 >> 0;

        if(!node.left) {
            node.left = new TreeNode(node.start, mid);
        }

        if(!node.right) {
            node.right = new TreeNode(mid+1, node.end);
        }

        node.val = Math.max(
            this.add(qs, qe, node.left),
            this.add(qs, qe, node.right),
        ) + node.booked;

        return node.val;
        
    }
    
    getMax() {
        return this.root.val;
    }
    
}

class TreeNode {
    constructor(start, end) {
        this.start = start;
        this.end = end;
        this.val = 0;
        this.booked = 0;
        this.left = this.right = null;
    }
}

var MyCalendarThree = function() {
    this.start = [];
    this.end = [];    
    this.k = 1;
};

MyCalendarThree.prototype.book = function(start, end) {
    this.start.push(start);
    this.start.sort((a,b) => a-b);
    this.end.push(end);
    this.end.sort((a,b) => a-b);
    let count = 0;
    let endIdx = 0;
    for(let i = 0; i < this.start.length; i++) {
        if(this.start[i] < this.end[endIdx]) {
            count += 1;  
        } else {
            endIdx += 1;
        }
    }
    this.k = Math.max(this.k, count);
    return this.k;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #732. My Calendar III

I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.


In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!