My Calendar II
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).
Consider 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.
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. This boundary rule matters for the overlap test below, where we use strict < rather than <=.
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 too large to index a fixed-size array by time. We need approaches that work with sparse intervals.- At most
1000calls tobook-> An O(n^2) total approach runs in about a million operations, which is fast enough. This rules out needing a balanced-tree or segment-tree solution for performance, though we cover the line sweep below because it generalizes better.
Approach 1: Brute Force (Two Lists)
Intuition
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).
The order of the two passes is what keeps this correct. We test against doubleBooked before adding any new regions, so the new event is never compared against an overlap it just produced with itself. Each region in doubleBooked came from a distinct pair of earlier events, so overlapping any of them means three events share a point.
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.
The next approach drops the separate overlap list. Instead of tracking which intervals overlap which, it counts how many events are active at each point in time and rejects a booking when that count would reach three.
Approach 2: Line Sweep with Sorted Map
Intuition
Each booking adds 1 to the active-event count at its start time and subtracts 1 at its end time. Process these changes in sorted time order while maintaining a running count, and that count equals the number of events active at every moment.
A triple booking occurs when the running count reaches 3. The algorithm tentatively adds the new booking's two deltas to the timeline, sweeps through the entries in sorted order, and checks whether the count ever hits 3. If it does, it undoes the addition and returns false. Otherwise it keeps the addition and returns true.
This is the line sweep (difference array) technique. Since the time range is up to 10^9, we store the deltas in a map keyed by time point (TreeMap in Java, a plain dict iterated in sorted order in Python) instead of an array. The map holds only the time points where some event starts or ends, so its size stays proportional to the number of bookings.
The running count is correct at every key because all deltas at or before that time point have been summed in time order, and overlaps change the count only at event boundaries. The maximum count over the whole sweep therefore equals the maximum number of simultaneously active events. The tentative-add-then-rollback structure avoids a separate pre-check: we add the booking, measure the new maximum directly, and undo the two deltas (cleaning up any entry that returns to zero) if it reaches 3. Rolling back leaves the timeline identical to its state before the call, so a rejected booking has no effect.
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.