My Calendar II
Medium · Trees · Array · Binary Search · Design · Segment Tree · Prefix Sum · Ordered Set
Problem
Build a calendar that allows events to overlap in pairs but rejects any event that would cause a triple booking: some moment covered by three events at once.
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 overlap one starting at t.
Implement MyCalendarTwo:
- MyCalendarTwo() creates an empty calendar.
- boolean book(int start, int end) adds the event and returns true if doing so creates no triple booking; 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 = ["MyCalendarTwo","book","book","book","book","book","book"], args = [[],[1,5],[3,8],[4,6],[5,7],[6,9],[8,10]] Output: [None, True, True, False, True, False, True]
[4,6) would make [4,5) triple-booked and [6,9) would do the same at [6,7). The others at most double up.
Input: ops = ["MyCalendarTwo","book","book","book"], args = [[],[0,2],[0,2],[2,4]] Output: [None, True, True, True]
Two identical events are allowed, and [2,4) starts where they end.
Input: ops = ["MyCalendarTwo","book","book","book","book"], args = [[],[10,20],[10,20],[15,16],[20,21]] Output: [None, True, True, False, True]
[15,16) lies inside a stretch that is already double-booked. [20,21) only touches it.
Constraints
- 0 <= start < end <= 10^9
- At most 1000 calls are made to book.
Approaches
- Sweep line over all events for each booking — time O(n log n) per booking, space O(n)
Follow-up
Generalize to "reject a booking that makes k events overlap" (My Calendar III asks for the largest overlap so far): keep a sorted map of +1/-1 changes and sweep it, or use a segment tree over compressed times with range add and range max for O(log n) per booking.
Related problems
Start free on Cariara · Coding problems · System design studio
