DSA problem
My Calendar I
Implement a MyCalendar class to store your events. A new event can be added if adding it will not cause a double booking. A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events). The event is represented as a pair of integers start and end denoting the half-open interval [start, end).
The class needs a single method book(start, end) that returns true if the event can be added without conflict (and adds it) or false otherwise (and does nothing). Two intervals [s1, e1) and [s2, e2) overlap iff s1 < e2 && s2 < e1, equivalently iff neither finishes before the other starts.
A naive O(n) per call solution stores the events in an unsorted list and scans them all on each book to check for overlap. With up to k calls this is O(k^2) total — workable for small k but slow for large k.
The optimal approach keeps the events in an ordered structure indexed by start. For each new (start, end) we look up the event immediately before start (its floor) and the event at or after start (its ceiling); only those two neighbors can possibly overlap with the new interval. If floor.end > start or ceiling.start < end, reject; otherwise insert. With a balanced BST / TreeMap each call costs O(log n), giving O(k log k) total. We illustrate that here in Java with TreeMap and C++ with std::map; other languages use an ordered structure or bisect/insort.
Examples
["MyCalendar","book","book","book"] [[],[10,20],[15,25],[20,30]][null,true,false,true]["MyCalendar","book","book"] [[],[1,5],[2,3]][null,true,false]["MyCalendar","book","book"] [[],[5,10],[10,15]][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.