DSA problem
My Calendar II
Implement a MyCalendarTwo class to store events. A new event can be added if adding it will not cause a triple booking. A triple booking is when three events have some non-empty intersection (a moment shared by all three). The event is the half-open interval [start, end).
The class exposes one method, book(start, end), that returns true if the event can be added without causing a triple booking (and adds it) or false otherwise (and does nothing). Compared to MyCalendar I, we now allow up to two events to overlap at any moment but no more than two.
A clean way to think about this is to maintain two lists: single for parts of the timeline covered by exactly one event so far, and overlap for parts covered by exactly two events so far. When booking [s, e): first scan overlap — if [s, e) intersects any interval in overlap, that would be a triple booking, so reject. Otherwise compute every intersection of [s, e) with intervals already in single and add those intersections to overlap; then add the new event itself to single.
The intersection of [s, e) with [a, b) is [max(s, a), min(e, b)) if that range is non-empty, and is empty otherwise. With k calls and naive lists this is O(k) per call and O(k^2) total — acceptable for the given constraints. A balanced BST keyed by start gives O(log k) per call with the same overall correctness.
Examples
["MyCalendarTwo","book","book","book","book","book","book"] [[],[10,20],[50,60],[10,40],[5,15],[5,10],[25,55]][null,true,true,true,false,true,true]["MyCalendarTwo","book","book","book"] [[],[1,10],[1,10],[1,10]][null,true,true,false]["MyCalendarTwo","book","book"] [[],[10,20],[15,25]][null,true,true]Constraints
- 0 <= start < end <= 10^9
- At most 1000 calls will be made to book.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.