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.
In this approach, we maintain two separate lists: `single_booked` for bookings that have been added without conflicts, and `double_booked` for intervals where two events overlap. To add a new booking:
The C solution defines two lists to store the single_booked and double_booked intervals. The `book` function checks for triple bookings by testing overlaps with double_booked, then adds any necessary doubles before adding the event to the single_booked list.
Time Complexity: O(N^2) because for each booking, we might need to check with all existing ones.
Space Complexity: O(N) to store all bookings.
In this approach, we use a segment tree to efficiently keep track of overlapping intervals. By maintaining a segment tree, we can:
This approach is optimal for datasets with large integer boundaries due to the logarithmic nature of segment trees for both update and query operations.
The C++ solution uses a `map` to simulate a segment tree on a line sweep basis. As intervals are booked or end, we increment or decrement from the timeline, respectively. The `book` method tracks active bookings to ensure it never surpasses two overlapping intervals.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N log N) due to map operations.
Space Complexity: O(N) for map storage.
We can use the concept of a difference array to record the booking status at each time point. Then, we traverse all the time points and count the booking status at the current time point. If the number of bookings exceeds 2, we return false. Otherwise, we return true.
The time complexity is O(n^2), and the space complexity is O(n), where n is the number of bookings.
Python
Java
C++
Go
TypeScript
JavaScript
A segment tree divides the entire interval into multiple non-contiguous subintervals, with the number of subintervals not exceeding log(width). To update the value of an element, only log(width) intervals need to be updated, and these intervals are all contained within a larger interval that includes the element. When modifying intervals, a lazy mark is used to ensure efficiency.
[1, N];[x, x];[l, r], its left child is [l, mid] and its right child is [mid + 1, r], where mid = \lfloor(l + r) / 2\rfloor (i.e., floor division).For this problem, the segment tree nodes maintain the following information:
vaddSince the time range is 10^9, which is very large, we use dynamic node creation.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of bookings.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Using Two Lists for Overlapping Intervals | Time Complexity: O(N^2) because for each booking, we might need to check with all existing ones. |
| Approach 2: Segment Tree for Interval Overlaps | Time Complexity: O(N log N) due to map operations. |
| Difference Array | — |
| Segment Tree | — |
| 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 |
My Calendar II - Leetcode 731 - Python • NeetCodeIO • 13,283 views views
Watch 9 more video solutions →Practice My Calendar II with our built-in code editor and test cases.
Practice on FleetCode