732. My Calendar III

Hello, reader 👋🏽 ! Welcome to day 7 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: My Calendar III.

🤔 Problem Statement

We are given n queries which contain the start and end interval of event that has to be booked in the calendar such that [start, end). For every event that needs to be booked, we have to return the maximum k events that intersect. That is all k events have some intersection in the time of event.

["MyCalendarThree","book","book","book","book","book","book"]
[[],[10,20],[50,60],[10,40],[5,15],[5,10],[25,55]]

• MyCalendarThree() initialises an object of MyCalendarThree class.
• book is an event of the signature: int book(int start, int end) and we are expected to return the maximum value k such that k events intersect.

From the above example when we book:

1. [10,20] : no intersection as it's the first event in the calendar, return 1.
2. [50,60] : no intersection as there's no overlapping with previous event, return 1.
3. [10,40] : intersects with event [10,20]. Both events overlap and happen simultaneously during the interval : [10, 20), return 2.
4. [5, 15] : intersects with events[10,20], [10,40]. All 3 events overlap and happen simultaneously during the interval [10,15), return 3.
5. [5,10]: intersects with event [5,15]. Both events overlap and happen simultaneously during interval [5,10). return 3 (since 3 > 2).
6. [25,55]: intersects with events [10,40] and [50,60]. Both events overlap and happen simultaneously during intervals [25, 40] and [50,55], return 3 (since 3 > 2).

💬 Initial Thought Process

• Not going to lie, but this problem was not as straight forward as it looked in the first go. After I completed this problem, I looked up and found that there are similar problems like. this and they use an algorithm called sweep-line to count intersections.
• I did not right away think of this (in fact, I didn't event think of it). I read and completely misunderstood the problem statement!
• I just kept adding intervals to a list and every time a new slot is to be booked, I keep track of the count of intersections and compare this [start, end) with the previous slots.
• Obviously, this wasn't the right solution because when we keep track of k max intersections, all the k slots must have some intersection with another.
• With the solution I had written, it didn't take into account common intersections. Rather it just kept track of all the intersections.

• So, I went ahead and started reading the solution and I realised that there are similar problems.

  • Calendar I
  • Calendar II
• And it was while solving the Calendar II problem that I understood line sweep algorithm.

Let's take up with the above example in a time line and represent all the intersections.

• From the above image, we can see that the max intersections is 3, and it occurs between [5,10].

Line Sweep Algorithm

• According to the sweep line algorithm, we represent several events as taking place on an imaginary line (or plane depends on intervals given).
• For the given range [start, end) we increase the count for the start point by 1 (representing an event began), and decrement the count for the end point by 1 (representing an event ended).
• For every point in the interval from the first start to the last end, we will add the values at the current point and compare it with the max bookings so far.

👩🏽‍💻 Solution - Line Sweep

• Below is the code for the discussed approach:

class MyCalendarThree {
    // We want sorted intervals. That is the smallest point of all booking [start, end)
    // must appear first
    // If we were to book 2 ranges [50,60], [10,20] => this will sort the ranges
    // 10, 20, 50, 60
    TreeMap<Integer, Integer> events;

    public MyCalendarThree() {
        events = new TreeMap();
    }

    public int book(int start, int end) {
        // Increment the count of start by 1
        events.put(start, events.getOrDefault(start,0)+1);
        // Decrement the count of end by 1
        events.put(end, events.getOrDefault(end,0)-1);

        // Get the max bookings so far with current and previous events.
        int maxBooking = 0, currBooking = 0;
        for(int booking: events.values()) {
            currBooking += booking;
            // If the value is greater than the previous maxBookings, update
            maxBooking = Math.max(maxBooking, currBooking);
        }

        return maxBooking;
    }
}

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree obj = new MyCalendarThree();
 * int param_1 = obj.book(start,end);
 */

Time Complexity: O(n) for every query
    - Since we will have to go through all the n given ranges
    - n => number of range intervals/ events
Space Complexity: O(n) for storing the key value pairs

• The problems states that the book() is called multiple times. If the book() is called n times, then the overall time complexity will be O(n^2).
• The time complexity can be improved by using a segment tree. But, I won't be discussing this approach.
• Check out the repository for the question here.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!