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:
MyCalendarThree() Initializes the object.int book(int startTime, int endTime) 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 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 <= 109400 calls will be made to book.This method uses a line sweep technique, where we process the critical points along the time axis. We treat each event start time as a +1 (which indicates a new event starts), and each end time as a -1 (indicating an event ends).
By maintaining a running sum, we can identify the maximum overlap of events, which gives us the maximum k-booking at any point.
In this Python implementation, we maintain a list of tuples representing time points and their effects (+1 or -1). We sort these time points and iterate over them to calculate the maximum overlapping intervals, thus obtaining the maximum k-booking.
Java
JavaScript
Time Complexity: O(N log N) due to sorting.
Space Complexity: O(N) for storing the timeline of events, where N is the number of events booked.
A more advanced approach involves using a balanced tree map (or balanced tree data structure) to manage events and efficiently find the maximum overlap.
The map holds start and end times as keys and their occurrences as values. By efficiently summing these up, we can determine the maximum k-booking.
This C# solution uses a SortedDictionary to act like a balanced binary search tree. We increment the value for a start time and decrement for an end time. The running sum of values reflects the number of active events at any time.
C++
Time Complexity: O(N log N) for the operations on a balanced tree.
Space Complexity: O(N) traversing the sorted keys when booking new events.
| Approach | Complexity |
|---|---|
| Sweep Line Approach | Time Complexity: O(N log N) due to sorting. |
| Balanced Tree Map Approach | Time Complexity: O(N log N) for the operations on a balanced tree. |
My Calendar II - Leetcode 731 - Python • NeetCodeIO • 11,150 views views
Watch 9 more video solutions →Practice My Calendar III with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor