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 [startTime, endTime), after each given event, return an integer k representing the maximum k-booking between all the previous events. Implement the MyCalendarThree class with methods to initialize the object and book events.
Key Insights
- Each event is represented by a start and end time.
- We need to track overlapping intervals to determine the maximum number of concurrent events (k-bookings).
- A simple array of events would be inefficient for checking overlaps as the number of events grows.
- Using a map or dictionary to track the start and end of events can efficiently determine overlaps.
- Each booking will potentially alter the count of concurrent events at specific time points.
Space and Time Complexity
Time Complexity: O(N log N) where N is the number of bookings, mainly due to sorting the events. Space Complexity: O(N) for storing the events in a dictionary.
Solution
The solution involves using a map (or dictionary) to keep track of the number of events starting and ending at each time point. When an event is booked, we increment the count at the start time and decrement it at the end time. We then traverse through the keys of this map to calculate the maximum overlap at any time. This approach allows us to efficiently compute the maximum k-booking after each event.