Watch 10 video solutions for My Calendar III, a hard level problem involving Binary Search, Design, Segment Tree. This walkthrough by Hua Hua has 4,397 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: Design a booking system where each event is an interval [start, end). After every booking, return the maximum number of overlapping events (k-booking) seen so far. The challenge is efficiently tracking overlaps as intervals are inserted one by one.
Approach 1: Sweep Line with Difference Map (O(n) per booking, O(n) space)
This method treats every interval as two events: +1 at start and -1 at end. Store these changes in an ordered structure and perform a prefix scan to compute active overlaps. Each time you book an event, increment the start position and decrement the end position, then iterate through the timeline accumulating the running sum. The maximum prefix value represents the highest number of concurrent events. This is a classic prefix sum style sweep that simulates a timeline of events.
The key insight: overlapping intervals translate into cumulative counts. When multiple events start before previous ones end, the prefix sum naturally grows. This approach is simple to implement and works well for the constraint size of the problem.
Approach 2: Balanced Tree Map (Ordered Map Sweep) (O(n) per booking, O(n) space)
Use a balanced ordered map (such as TreeMap or std::map) to store time points and their delta changes. Insert +1 at the start and -1 at the end of each interval. Because the structure keeps keys sorted, you can iterate through the map to compute the running prefix sum and track the maximum overlap. The ordered structure ensures updates happen in O(log n), while the sweep to compute the maximum takes O(n).
This approach is essentially a structured version of the sweep line technique often used in interval problems and computational geometry. Using an ordered set / map guarantees sorted traversal without extra sorting overhead.
For larger-scale versions of this problem, advanced solutions rely on a dynamic segment tree to track range updates and maximum overlaps in O(log n). That structure is more complex but scales better when the number of bookings becomes very large.
Recommended for interviews: The sweep line with an ordered map is the expected solution. It shows clear understanding of interval overlap problems and prefix accumulation. Explaining the difference-array idea demonstrates strong algorithmic intuition, while mentioning a segment tree extension shows awareness of scalable designs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sweep Line with Difference Map | O(n) per booking | O(n) | Best for moderate constraints where simplicity and clarity matter |
| Balanced Tree Map (Ordered Map) | O(n) per booking, O(log n) update | O(n) | Preferred in languages with built-in ordered maps like C++ or C# |