My Calendar II
Last Updated: March 29, 2026
Understanding the Problem
We are building a calendar that accepts bookings one at a time. Each booking is a half-open interval [start, end). We allow double bookings (two events overlapping), but we must reject any booking that would create a triple booking (three events all overlapping at the same moment).
The key is understanding what "triple booking" means concretely. If we already have bookings [10, 20) and [10, 40), the overlap region [10, 20) is double-booked. If a new booking [5, 15) comes in, the region [10, 15) would overlap with both existing bookings, creating a triple booking. So we reject it.
Notice that the intervals are half-open: [start, end) means start is included but end is not. So [10, 20) and [20, 30) do not overlap, since 20 belongs to the second interval but not the first.
The core challenge is efficiently tracking where double bookings exist, so we can quickly check whether a new event would turn any double booking into a triple booking.
Key Constraints:
0 <= start < end <= 10^9-> The time range is huge, so we cannot use a fixed-size array indexed by time. We need approaches that work with sparse intervals.- At most
1000calls tobook-> With only 1000 operations, even an O(n^2) approach per call runs in about a million operations total. That is perfectly fine.
Approach 1: Brute Force (Two Lists)
Intuition
The most natural way to think about this: keep one list of all accepted bookings and a separate list of all double-booked regions. When a new event [start, end) comes in, we do two checks:
- Does the new event overlap with any region that is already double-booked? If yes, adding this event would create a triple booking, so reject it.
- If no triple booking would occur, compute the overlap between the new event and every existing single booking. Each such overlap becomes a new double-booked region. Then add the new event to the bookings list.
The overlap between two half-open intervals [s1, e1) and [s2, e2) is [max(s1, s2), min(e1, e2)). This overlap is non-empty only when max(s1, s2) < min(e1, e2).
This is essentially a two-pass approach: first pass checks for rejection, second pass updates the state.
Algorithm
- Maintain two lists:
bookings(all accepted events) anddoubleBooked(all double-booked regions). - When
book(start, end)is called: - For each interval
[ds, de)indoubleBooked, check ifmax(start, ds) < min(end, de). If any such overlap exists, returnfalse. - For each interval
[bs, be)inbookings, compute the overlap[max(start, bs), min(end, be)). If this overlap is non-empty, add it todoubleBooked. - Add
[start, end)tobookings. - Return
true.
Example Walkthrough
Code
- Time Complexity: O(n) per
bookcall, where n is the number of previously booked events. We scan both thedoubleBookedlist and thebookingslist, each of which can have up to n entries. Over all calls, this gives O(n^2) total. - Space Complexity: O(n^2) in the worst case. Every pair of bookings can create an overlap, so the
doubleBookedlist could grow quadratically.
This approach works correctly but the double-booked list can grow quadratically. What if instead of tracking individual overlaps, we used a single data structure that tells us exactly how many events are active at any point in time?
Approach 2: Line Sweep with Sorted Map
Intuition
Here is a fundamentally different way to think about the problem. Instead of tracking which intervals overlap with which, imagine a timeline. Each booking adds 1 to the "event count" at its start time and subtracts 1 at its end time. If we process these events in sorted order and maintain a running count, we know exactly how many events are active at every moment.
A triple booking occurs when the running count reaches 3. So the algorithm is: tentatively add the new booking's events to the timeline, sweep through the events in order, and check if the count ever hits 3. If it does, undo the addition and return false. If it never does, keep the addition and return true.
This is the classic line sweep (or difference array) technique, but since the time range is up to 10^9, we use a sorted map (TreeMap in Java, SortedDict in Python) instead of an array. The map only stores time points where events start or end, keeping it sparse and efficient.
The line sweep technique converts a spatial problem (overlapping intervals) into a temporal scanning problem. By recording +1 at each interval start and -1 at each interval end, then sweeping left to right, we reconstruct exactly how many intervals are active at each point. This is the same idea behind the difference array technique used in problems like Car Pooling and Corporate Flight Bookings.
The "tentatively add, then check, then maybe undo" pattern is a clean way to handle the booking logic. Instead of pre-checking whether the new interval would cause a problem (which requires reasoning about existing overlaps), we just add it and see what happens. If the answer is bad, we roll back.
Algorithm
- Maintain a sorted map
timelinewhere each key is a time point and each value is the net change in active events at that time. - When
book(start, end)is called: - Add
+1totimeline[start]and-1totimeline[end]. - Sweep through the map in sorted key order, accumulating a running count.
- If the running count ever reaches 3, undo the changes (subtract 1 from
timeline[start], add 1 totimeline[end]), clean up zero entries, and returnfalse. - If the sweep completes without hitting 3, return
true.
Example Walkthrough
Code
- Time Complexity: O(n) per
bookcall for languages with built-in sorted maps (Java TreeMap, C++ map, C# SortedDictionary), since the sweep iterates through all entries. O(n log n) per call for JavaScript/TypeScript due to sorting the keys. Over all n calls, this is O(n^2) total. - Space Complexity: O(n) for the sorted map. Each booking adds at most 2 entries, and entries are cleaned up when their count reaches zero.