Watch 10 video solutions for My Calendar II, a medium level problem involving Array, Binary Search, Design. This walkthrough by NeetCodeIO has 13,283 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.
A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).
The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < endTime.
Implement the MyCalendarTwo class:
MyCalendarTwo() Initializes the calendar object.boolean book(int startTime, int endTime) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.
Example 1:
Input ["MyCalendarTwo", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]] Output [null, true, true, true, false, true, true] Explanation MyCalendarTwo myCalendarTwo = new MyCalendarTwo(); myCalendarTwo.book(10, 20); // return True, The event can be booked. myCalendarTwo.book(50, 60); // return True, The event can be booked. myCalendarTwo.book(10, 40); // return True, The event can be double booked. myCalendarTwo.book(5, 15); // return False, The event cannot be booked, because it would result in a triple booking. myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked. myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.
Constraints:
0 <= start < end <= 1091000 calls will be made to book.Problem Overview: You need to design a calendar that supports booking events represented as half-open intervals [start, end). A booking is allowed if it does not create a triple booking. Double bookings are fine, but three overlapping events at the same time must be rejected.
Approach 1: Using Two Lists for Overlapping Intervals (O(n) per booking, O(n) space)
This approach tracks two lists: bookings (all accepted events) and overlaps (intervals that are already double booked). When a new event arrives, first check if it overlaps with anything in overlaps. If it does, the booking would create a triple overlap, so reject it immediately.
If it passes that check, iterate through existing bookings. For every interval that intersects with the new one, compute the intersection and add that range to overlaps. This records the newly created double-booked region. Finally, add the new interval to bookings. The key insight: instead of tracking counts everywhere, explicitly track the ranges where double booking already exists.
This method relies heavily on interval intersection logic and sequential scans using an array. Each booking may compare with all previous events, giving O(n) time per operation and O(n^2) total across all calls in the worst case.
Approach 2: Segment Tree for Interval Overlaps (O(log C) per booking, O(n log C) space)
When the time range becomes large (up to 10^9), scanning intervals repeatedly becomes inefficient. A dynamic segment tree solves this by storing the maximum booking count for each range. Each node represents a segment of time and keeps track of the maximum overlap inside that range.
For every booking request, query the tree to check the maximum overlap in [start, end). If the value is already 2, adding another event would create a triple booking, so reject it. Otherwise, update the range by incrementing its count. Lazy propagation allows efficient range updates without expanding the entire tree.
This method treats the problem as a range frequency update problem similar to sweep-line or prefix sum techniques, but implemented with a tree so queries stay logarithmic. Each booking runs in O(log C) time where C is the coordinate range.
Recommended for interviews: The two-list interval method is the most commonly expected answer. It is short, easy to reason about, and demonstrates clear understanding of interval overlaps. The segment tree approach shows deeper knowledge of advanced data structures and range queries, which can impress in system-heavy or follow-up interview questions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Lists for Overlapping Intervals | O(n) per booking, O(n^2) total | O(n) | Best for interviews and moderate constraints; simple logic using interval comparisons |
| Segment Tree with Lazy Propagation | O(log C) per booking | O(n log C) | When time coordinates are large and frequent range queries or updates are required |