My Calendar III
Hard · Intervals · Design · Ordered Map · Prefix Sum · Segment Tree
Problem
A k-booking happens when k events share some moment in time. An event is a half-open interval [startTime, endTime): it covers every real x with startTime <= x < endTime, so an event that ends at t does not overlap one that starts at t.
Implement MyCalendarThree:
- MyCalendarThree() creates an empty calendar.
- int book(int startTime, int endTime) adds the event (bookings are never refused) and returns the largest k such that some k-booking exists among all the events booked so far.
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 = ["MyCalendarThree","book","book","book","book"], args = [[],[5,10],[8,15],[9,12],[15,20]] Output: [None, 1, 2, 3, 3]
After the third booking all three events cover time 9. [15,20) starts exactly when [8,15) ends, so the maximum stays 3.
Input: ops = ["MyCalendarThree","book","book"], args = [[],[1,3],[3,6]] Output: [None, 1, 1]
The second event starts when the first ends, so they never overlap.
Input: ops = ["MyCalendarThree","book","book","book","book"], args = [[],[0,100],[10,20],[12,15],[50,60]] Output: [None, 1, 2, 3, 3]
Three events nest around time 12; [50,60) only overlaps the outer one.
Constraints
- 0 <= startTime < endTime <= 10^9
- At most 400 calls are made to book.
Approaches
- Count overlaps at every start — time O(n²) per book, space O(n)
Follow-up
With up to 10^5 calls the O(n) sweep per call is too slow. A segment tree over the compressed (or dynamically created) time range, storing the maximum overlap with lazy range additions, answers each book in O(log C): add 1 to [startTime, endTime) and read the root maximum.
Related problems
Start free on Cariara · Coding problems · System design studio
