My Calendar III

Problem Statement

The problem revolves around tracking overlapping intervals or events in a simulated calendar system and determining the maximum level of overlap at any given time, referred to as k-booking. Specifically, a k-booking occurs when k distinct events share at least one common time point.

To manage and query these intervals, you are required to implement a class, MyCalendarThree, which supports:

1. MyCalendarThree() - Constructor that initializes the new object.
2. int book(int startTime, int endTime) - Method to add a new event to the calendar that starts at startTime and ends just before endTime. Post each booking, this function should return the maximum number k which indicates the highest number of overlapping events until that point in time.

The intervals are defined using a half-open interval notation [startTime, endTime), which includes startTime but excludes endTime.

Examples

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
myCalendarThree.book(50, 60); // return 1
myCalendarThree.book(10, 40); // return 2
myCalendarThree.book(5, 15);  // return 3
myCalendarThree.book(5, 10);  // return 3
myCalendarThree.book(25, 55); // return 3

Constraints

• 0 <= startTime < endTime <= 10⁹
• At most 400 calls will be made to book.

Approach and Intuition

To handle the bookings and check the overlaps effectively, the following approach can be adopted:

1. Timeline Sweep with Counters: Treat each booking as two events:

   • +1 at startTime (event starts)
   • -1 at endTime (event ends) Maintain a counter map that tracks how many events are active at any given time.

2. Booking Operation:

   • On every book(start, end) call:

     • Increment the value at start and decrement at end in a TreeMap or SortedDict.
     • Iterate over the time points in order and maintain a running sum of active events.
     • Track the peak of this running sum, which gives the updated max overlap k.

3. Why it Works Efficiently:

   • Since we only make at most 400 calls, and we only update/query a limited set of time points, this approach runs in acceptable time.
   • Using a TreeMap-like structure keeps insertions and iteration in O(log N) or O(N) where N is the number of unique time points.

4. Illustration: For bookings like:

   • [10, 20] → overlap 1
   • [10, 40] → overlaps with previous → overlap 2
   • [5, 15] → overlaps both → peak overlap 3

This design efficiently simulates the booking system and dynamically tracks the maximum concurrent events.

Solutions

class CalendarMaxOverlap {
private:
    map<int, int> events;
    int maxOverlap;
    
public:
    CalendarMaxOverlap() {
        events[0] = 0;
        events[1000000001] = 0;
        maxOverlap = 0;
    }
    
    void insertPoint(int point) { events[point] = (--events.upper_bound(point))->second; }
    
    int bookEvent(int start, int end) {
        insertPoint(start), insertPoint(end);
        for (auto iter = events.find(start); iter->first < end; ++iter) {
            maxOverlap = max(maxOverlap, ++(iter->second));
        }
        return maxOverlap;
    }
};