[Google Question][LeetCode] My Calendar III

Problem: 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:

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

Approach: If you see this is kind of same problem as finding the maximum number of platforms given arrival and departure times of trains. The difference here is here the arrival and departure time are coming one by one instead of having all the times in one go so we can use something like a balanced binary search tree to insert these timings instead of sorting the input lists.

Off course we can maintain two such binary search trees for start and end time but do we really need it. If you see in our previous problem if we merge both sorted arrival and departure arrays, our problem will become "Incrementing the number of platform required by 1 if an arrival time comes and decrement the number of platform required by 1 if a departure time comes."

Here also we just create one balanced binary search tree and then we can use the same approach. I am using SortedDictionary which is kind of balanced binary search tree.

Implementation in C#:

public class MyCalendarThree 

{

    public MyCalendarThree() 

    {

        this.times = new SortedDictionary<int, int>();

    }

    

    public int Book(int start, int end) 

    {

        if (!this.times.ContainsKey(start))

        {

            this.times[start] = 0;

        }

        ++this.times[start];

        if (!this.times.ContainsKey(end))

        {

            this.times[end] = 0;

        }

        --this.times[end];

        int maxK = 0;

        int currIntersections = 0;

        foreach (KeyValuePair<int, int> time in times)

        {

            currIntersections += time.Value;

            maxK = Math.Max(maxK, currIntersections);

        } 

        return maxK;

    }

    

    private SortedDictionary<int, int> times;

}

Complexity: O(n^2) + O(nlogn) => O(n^2)