The problem
Implement book(start, end): add the half-open event [start, end) only if it does not double-book with any existing event.
Stuck? Reveal hints one at a time
How to approach it
- 1Keep events sorted by start (sorted array + binary search, or an ordered map / red-black tree).
- 2Locate the insertion point for the new start.
- 3Check the predecessor (its end must be ≤ new start) and the successor (its start must be ≥ new end).
- 4Both clear → insert and return true; else false.
Key insight
In a sorted-by-start, non-overlapping calendar, only the two adjacent events can possibly conflict — ordering shrinks the check from O(n) comparisons to two.
The solution
Watch out for
- Half-open intervals: [1,5) and [5,10) do NOT overlap — use ≤/≥, not </>.
- Languages with real ordered maps (C++ std::map, Java TreeMap) make both steps O(log n) — say so in interviews.