My Calendar I
Medium · Trees · Array · Binary Search · Design · Segment Tree · Ordered Set
Problem
Build a calendar that accepts a new event only if it does not cause a double booking, meaning two events overlap in time.
An event is a half-open interval [start, end): it covers every real x with start <= x < end, so an event ending at time t does not clash with one starting at t.
Implement MyCalendar:
- MyCalendar() creates an empty calendar.
- boolean book(int start, int end) adds the event and returns true if it overlaps no existing event; otherwise it leaves the calendar unchanged and returns false.
Each test is a list of calls: ops[i] is the method name (the first is the class) and args[i] its arguments. The expected output lists each call’s return value, None for the constructor.
Examples
Input: ops = ["MyCalendar","book","book","book","book"], args = [[],[5,10],[8,12],[10,15],[1,5]] Output: [None, True, False, True, True]
[8,12) overlaps [5,10); [10,15) and [1,5) only touch it at the endpoints.
Input: ops = ["MyCalendar","book","book"], args = [[],[0,100],[50,51]] Output: [None, True, False]
The second event lies inside the first.
Input: ops = ["MyCalendar","book","book","book","book"], args = [[],[0,10],[20,30],[12,21],[10,20]] Output: [None, True, True, False, True]
[12,21) runs into [20,30). [10,20) fills the gap exactly.
Constraints
- 0 <= start < end <= 10^9
- At most 1000 calls are made to book.
Approaches
- Check every booked event — time O(n) per booking, space O(n)
Follow-up
With far more bookings, Python’s list insert (O(n) memory moves) becomes the bottleneck. A balanced tree (SortedList from sortedcontainers, TreeMap, std::map) makes both the lookup and the insert O(log n). If double bookings were allowed but triple ones were not, keep a second structure of the stretches that are already double-booked and check the new event against it.
Related problems
Start free on Cariara · Coding problems · System design studio
