My Calendar III
HardPrompt
A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.)
You are given some events [startTime, endTime), after each given event, return an integer k representing the maximum k-booking between all the previous events.
Implement the MyCalendarThree class:
MyCalendarThree()Initializes the object.int book(int startTime, int endTime)Returns an integerkrepresenting the largest integer such that there exists ak-booking in the calendar.
Example 1:
Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]
Explanation
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // return 1
myCalendarThree.book(50, 60); // return 1
myCalendarThree.book(10, 40); // return 2
myCalendarThree.book(5, 15); // return 3
myCalendarThree.book(5, 10); // return 3
myCalendarThree.book(25, 55); // return 3
Constraints:
0 <= startTime < endTime <= 109- At most
400calls will be made tobook.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves storing all events and, for each book call, recalculating the maximum overlap from scratch. We identify all unique start and end times (endpoints) from the booked events. The maximum overlap must occur at one of these start times. Therefore, we can iterate through each unique endpoint and count how many intervals are active at that specific moment. The highest count we find is the maximum k-booking.
Algorithm
- Maintain a list of all booked events.
- For each
bookcall, add the new event to the list. - To find the maximum k-booking, create a set of all unique start and end times from the list of events. These are the critical points where the number of overlapping events can change.
- Iterate through each unique point
p. - For each point
p, iterate through all the booked events and count how many of them are active at timep(i.e.,event.start <= p < event.end). - Keep track of the maximum count found across all points. This maximum count is the result.
Walkthrough
In this brute-force method, we maintain a simple list of all the event intervals that have been booked. When a new book(start, end) request comes in, we first add the new interval [start, end) to our list.
The core idea is that the number of concurrent events, or overlaps, can only change at the start or end time of an event. Therefore, to find the maximum number of overlaps, we only need to check these specific time points. We gather all unique start and end times from our list of events into a collection, for instance, a TreeSet to keep them sorted and unique.
Then, we iterate through each of these unique time points. For each point, we scan through our entire list of booked events and count how many of them contain this point. The maximum count found during this process is the maximum k-booking for the current set of events. While simple to grasp, this method is computationally expensive because it re-evaluates all events and all critical points for every single book call.
import java.util.ArrayList;import java.util.List;import java.util.Set;import java.util.TreeSet; class MyCalendarThree { private List<int[]> books; public MyCalendarThree() { books = new ArrayList<>(); } public int book(int startTime, int endTime) { books.add(new int[]{startTime, endTime}); Set<Integer> points = new TreeSet<>(); for (int[] b : books) { points.add(b[0]); // We only need to check start points, as the overlap count // is constant between any two consecutive endpoints. } int maxK = 0; if (books.isEmpty()) { return 0; } // The maximum overlap will occur at some event's start time. for (int point : points) { int currentK = 0; for (int[] b : books) { if (b[0] <= point && point < b[1]) { currentK++; } } maxK = Math.max(maxK, currentK); } return maxK; }}Complexity
Time
O(N^2) per `book` call. After N calls, there are N events and at most 2N unique endpoints. Iterating through O(N) points and for each point, iterating through N events results in O(N^2) complexity.
Space
O(N), where N is the number of calls to `book`. We need to store N events, and there are at most 2N unique endpoints.
Trade-offs
Pros
Simple to understand and implement.
Requires minimal data structures, just a list and a set.
Cons
The time complexity of O(N^2) per
bookcall makes it inefficient, especially as the number of eventsNgrows.The total time complexity over all calls can be up to O(N^3), which might be too slow and lead to a 'Time Limit Exceeded' error in a competitive programming context.
This approach, often called Boundary Counting or Difference Array, is based on a key insight: the number of overlapping events only changes at the start and end times of the intervals. We can think of a startTime as an event that increases the overlap count by one, and an endTime as an event that decreases it by one. By processing these +1 and -1 changes in chronological order, we can find the maximum overlap at any point in time. A sorted map, like Java's TreeMap, is ideal for storing these time points and their associated changes, as it automatically keeps them in sorted order.
Algorithm
- Use a
TreeMapto store the changes in the number of active events at specific time points. The keys of the map are the time points, and the values are the net change (+1 for a start, -1 for an end). - For each
book(start, end)call:- Increment the value at key
startby 1. If the key doesn't exist, it's equivalent to setting it to 1. - Decrement the value at key
endby 1. This marks the end of the interval.
- Increment the value at key
- To find the maximum k-booking, iterate through the values of the
TreeMap(which are naturally sorted by time). - Maintain a running sum of the active events (
currentK) and a maximum sum (maxK). - As you iterate, add the value (the change) to
currentKand updatemaxK = max(maxK, currentK). - The final
maxKis the answer.
Walkthrough
Instead of re-calculating from scratch every time, we can maintain a data structure that tracks the net change of events at each endpoint. A TreeMap is perfect for this, mapping time points to the change in the number of active events.
For each call to book(start, end):
- We record that at
startTime, one new event begins. We do this by incrementing the value associated with the keystartin ourTreeMap.timeline.put(start, timeline.getOrDefault(start, 0) + 1); - Similarly, at
endTime, one event concludes. We record this by decrementing the value for the keyend.timeline.put(end, timeline.getOrDefault(end, 0) - 1);
After updating the map for the new event, we can determine the maximum number of concurrent events. Since the TreeMap keeps the keys (time points) sorted, we can iterate through its values in chronological order. We maintain a running count of active events. By sweeping through the timeline, we add each change to our running count. The peak value this running count reaches is the maximum k-booking.
import java.util.TreeMap; class MyCalendarThree { private TreeMap<Integer, Integer> timeline; public MyCalendarThree() { timeline = new TreeMap<>(); } public int book(int startTime, int endTime) { // +1 for a new event starting timeline.put(startTime, timeline.getOrDefault(startTime, 0) + 1); // -1 for an event ending timeline.put(endTime, timeline.getOrDefault(endTime, 0) - 1); int maxK = 0; int currentK = 0; // Sweep through the timeline to find the max overlap for (int count : timeline.values()) { currentK += count; maxK = Math.max(maxK, currentK); } return maxK; }}Complexity
Time
O(N) per `book` call. Each `book` call involves two O(log N) operations on the `TreeMap` for updates. The subsequent sweep through the map takes O(N) time as there are at most 2N entries. The linear scan dominates the complexity.
Space
O(N), where N is the number of calls to `book`. The `TreeMap` will store at most 2N distinct endpoints.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Conceptually elegant and a common technique for interval-based problems.
The state (the timeline) is updated incrementally, avoiding recalculation.
Cons
While much better than brute force, it still requires a linear scan through all distinct endpoints for each
bookcall, which could be optimized further.
The most efficient solution utilizes a Segment Tree with Lazy Propagation. This data structure is designed for handling range updates and range queries efficiently. Each book(start, end) call corresponds to incrementing all values in the range [start, end-1] by one. The maximum k-booking is then the maximum value over the entire range. To handle the large coordinate space (0 to 10^9), we use a dynamic or implicit segment tree, where nodes are created on-the-fly as they are accessed, avoiding the need to pre-allocate a massive tree.
Algorithm
- The problem can be modeled as range updates and a global max query. A Segment Tree is a suitable data structure for this.
- Since the time coordinates can be very large (up to 10^9), a standard array-based segment tree is not feasible. We use a Dynamic Segment Tree (or Implicit Segment Tree), where nodes are created only when needed.
- Each node in the tree represents a time interval and stores
maxVal(the max k-booking in its range) and alazytag for pending updates. - For each
book(start, end)call, we perform a range update on the segment tree for the interval[start, end-1], incrementing the count by 1. - The update operation uses lazy propagation. When an update fully covers a node's range, we update its
lazytag andmaxValand stop descending. For partial overlaps, we first push the lazy value down to children and then recurse. - After each update, the
maxValof the root node will hold the maximum k-booking over the entire timeline.
Walkthrough
A Segment Tree is a powerful tree data structure that allows for efficient range queries and updates. In our case, a book(start, end) operation is an update on the range [start, end-1] (incrementing by 1), and we need to find the maximum value in the entire tree after each update.
The challenge is the vast range of time coordinates (0 to 10^9). A standard segment tree would require an array of an impossible size. The solution is a Dynamic Segment Tree, where each node is an object with pointers to its left and right children, which are initially null. A node is created only when a query or update needs to traverse to it.
To make range updates efficient, we use lazy propagation. When an update range completely covers a node's interval, we don't update all its descendant leaves. Instead, we store a lazy value at that node (e.g., +1) and update its maxVal. This lazy value is 'pushed down' to its children only when we need to traverse past this node in a future operation.
For each book(start, end) call, we call an update function on our segment tree. After the O(log C) update operation is complete, the maxVal stored at the root of the tree gives us the global maximum k-booking.
class MyCalendarThree { private static class Node { int maxVal; int lazy; Node left, right; Node() { this.maxVal = 0; this.lazy = 0; this.left = null; this.right = null; } } private Node root; private final int MAX_COORD = 1_000_000_000; public MyCalendarThree() { root = new Node(); } public int book(int startTime, int endTime) { // The interval is [startTime, endTime), so we update up to endTime - 1. update(root, 0, MAX_COORD, startTime, endTime - 1); return root.maxVal; } private void push(Node node) { if (node.lazy > 0) { if (node.left == null) node.left = new Node(); if (node.right == null) node.right = new Node(); node.left.lazy += node.lazy; node.left.maxVal += node.lazy; node.right.lazy += node.lazy; node.right.maxVal += node.lazy; node.lazy = 0; } } private void update(Node node, int nodeL, int nodeR, int queryL, int queryR) { // Full overlap: update lazy tag and max value, then return. if (queryL <= nodeL && nodeR <= queryR) { node.lazy += 1; node.maxVal += 1; return; } // Before recursing, push down lazy values. push(node); int mid = nodeL + (nodeR - nodeL) / 2; // Recurse on children based on overlap. if (queryL <= mid) { if (node.left == null) node.left = new Node(); update(node.left, nodeL, mid, queryL, queryR); } if (queryR > mid) { if (node.right == null) node.right = new Node(); update(node.right, mid + 1, nodeR, queryL, queryR); } // After children are updated, pull their max value up. int leftMax = (node.left != null) ? node.left.maxVal : 0; int rightMax = (node.right != null) ? node.right.maxVal : 0; node.maxVal = Math.max(leftMax, rightMax); }}Complexity
Time
O(log C) per `book` call. Each update on the segment tree traverses a path from the root, taking logarithmic time relative to the size of the coordinate range C.
Space
O(N * log C), where N is the number of `book` calls and C is the maximum coordinate value (10^9). Each update can create O(log C) new nodes.
Trade-offs
Pros
Extremely efficient time complexity per operation.
This is the optimal approach for this type of problem (range updates, max query).
Scales well even if the number of
bookcalls were much larger.
Cons
Implementation is significantly more complex than the other approaches.
The space complexity, while manageable for the given constraints, depends on both the number of calls
Nand the logarithm of the coordinate rangeC.
Solutions
Solution
class Node { Node left ; Node right ; int l ; int r ; int mid ; int v ; int add ; public Node ( int l , int r ) { this . l = l ; this . r = r ; this . mid = ( l + r ) >> 1 ; } } class SegmentTree { private Node root = new Node ( 1 , ( int ) 1 e9 + 1 ); public SegmentTree () { } public void modify ( int l , int r , int v ) { modify ( l , r , v , root ); } public void modify ( int l , int r , int v , Node node ) { if ( l > r ) { return ; } if ( node . l >= l && node . r <= r ) { node . v += v ; node . add += v ; return ; } pushdown ( node ); if ( l <= node . mid ) { modify ( l , r , v , node . left ); } if ( r > node . mid ) { modify ( l , r , v , node . right ); } pushup ( node ); } public int query ( int l , int r ) { return query ( l , r , root ); } public int query ( int l , int r , Node node ) { if ( l > r ) { return 0 ; } if ( node . l >= l && node . r <= r ) { return node . v ; } pushdown ( node ); int v = 0 ; if ( l <= node . mid ) { v = Math . max ( v , query ( l , r , node . left )); } if ( r > node . mid ) { v = Math . max ( v , query ( l , r , node . right )); } return v ; } public void pushup ( Node node ) { node . v = Math . max ( node . left . v , node . right . v ); } public void pushdown ( Node node ) { if ( node . left == null ) { node . left = new Node ( node . l , node . mid ); } if ( node . right == null ) { node . right = new Node ( node . mid + 1 , node . r ); } if ( node . add != 0 ) { Node left = node . left , right = node . right ; left . add += node . add ; right . add += node . add ; left . v += node . add ; right . v += node . add ; node . add = 0 ; } } } class MyCalendarThree { private SegmentTree tree = new SegmentTree (); public MyCalendarThree () { } public int book ( int start , int end ) { tree . modify ( start + 1 , end , 1 ); return tree . query ( 1 , ( int ) 1 e9 + 1 ); } } /** * Your MyCalendarThree object will be instantiated and called as such: * MyCalendarThree obj = new MyCalendarThree(); * int param_1 = obj.book(start,end); */class Node { public: Node * left ; Node * right ; int l ; int r ; int mid ; int v ; int add ; Node ( int l , int r ) { this -> l = l ; this -> r = r ; this -> mid = ( l + r ) >> 1 ; this -> left = this -> right = nullptr ; v = add = 0 ; } }; class SegmentTree { private: Node * root ; public: SegmentTree () { root = new Node ( 1 , 1e9 + 1 ); } void modify ( int l , int r , int v ) { modify ( l , r , v , root ); } void modify ( int l , int r , int v , Node * node ) { if ( l > r ) return ; if ( node -> l >= l && node -> r <= r ) { node -> v += v ; node -> add += v ; return ; } pushdown ( node ); if ( l <= node -> mid ) modify ( l , r , v , node -> left ); if ( r > node -> mid ) modify ( l , r , v , node -> right ); pushup ( node ); } int query ( int l , int r ) { return query ( l , r , root ); } int query ( int l , int r , Node * node ) { if ( l > r ) return 0 ; if ( node -> l >= l && node -> r <= r ) return node -> v ; pushdown ( node ); int v = 0 ; if ( l <= node -> mid ) v = max ( v , query ( l , r , node -> left )); if ( r > node -> mid ) v = max ( v , query ( l , r , node -> right )); return v ; } void pushup ( Node * node ) { node -> v = max ( node -> left -> v , node -> right -> v ); } void pushdown ( Node * node ) { if ( ! node -> left ) node -> left = new Node ( node -> l , node -> mid ); if ( ! node -> right ) node -> right = new Node ( node -> mid + 1 , node -> r ); if ( node -> add ) { Node * left = node -> left ; Node * right = node -> right ; left -> v += node -> add ; right -> v += node -> add ; left -> add += node -> add ; right -> add += node -> add ; node -> add = 0 ; } } }; class MyCalendarThree { public: SegmentTree * tree ; MyCalendarThree () { tree = new SegmentTree (); } int book ( int start , int end ) { tree -> modify ( start + 1 , end , 1 ); return tree -> query ( 1 , 1e9 + 1 ); } }; /** * Your MyCalendarThree object will be instantiated and called as such: * MyCalendarThree* obj = new MyCalendarThree(); * int param_1 = obj->book(start,end); */from sortedcontainers import SortedDict class MyCalendarThree : def __init__ ( self ): self . timeline = SortedDict () def book ( self , start : int , end : int ) -> int : self . timeline [ start ] = self . timeline . get ( start , 0 ) + 1 self . timeline [ end ] = self . timeline . get ( end , 0 ) - 1 return max ( accumulate ( list ( self . timeline . values ()))) ############ class Node : def __init__ ( self , l , r ): self . left = None self . right = None self . l = l self . r = r self . mid = ( l + r ) >> 1 self . v = 0 self . add = 0 class SegmentTree : # <=== def __init__ ( self ): self . root = Node ( 1 , int ( 1e9 + 1 )) def modify ( self , l , r , v , node = None ): if l > r : return if node is None : node = self . root if node . l >= l and node . r <= r : node . v += v node . add += v return self . pushdown ( node ) if l <= node . mid : self . modify ( l , r , v , node . left ) if r > node . mid : self . modify ( l , r , v , node . right ) self . pushup ( node ) def query ( self , l , r , node = None ): if l > r : return 0 if node is None : node = self . root if node . l >= l and node . r <= r : return node . v self . pushdown ( node ) v = 0 if l <= node . mid : v = max ( v , self . query ( l , r , node . left )) if r > node . mid : v = max ( v , self . query ( l , r , node . right )) return v def pushup ( self , node ): node . v = max ( node . left . v , node . right . v ) def pushdown ( self , node ): if node . left is None : node . left = Node ( node . l , node . mid ) if node . right is None : node . right = Node ( node . mid + 1 , node . r ) if node . add : node . left . v += node . add node . right . v += node . add node . left . add += node . add node . right . add += node . add node . add = 0 class MyCalendarThree : def __init__ ( self ): self . tree = SegmentTree () def book ( self , start : int , end : int ) -> int : self . tree . modify ( start + 1 , end , 1 ) return self . tree . query ( 1 , int ( 1e9 + 1 )) # Your MyCalendarThree object will be instantiated and called as such: # obj = MyCalendarThree() # param_1 = obj.book(start,end) ############ class Node ( object ): def __init__ ( self , start , end , c ): self . start = start self . end = end self . count = c self . left = None self . right = None class MyCalendarThree ( object ): def __init__ ( self ): self . root = None self . maxK = 1 def book_helper ( self , root , start , end , c ): if root == None : return Node ( start , end , c ) if start >= root . end : #不能写成return self.boook_helper()，因为要进行树的构建和修改，一定要赋值给root.right root . right = self . book_helper ( root . right , start , end , c ) elif end <= root . start : root . left = self . book_helper ( root . left , start , end , c ) else : intervals = sorted ([ start , end , root . start , root . end ]) root_l , root_r = root . start , root . end root . start , root . end = intervals [ 1 ], intervals [ 2 ] root . left = self . book_helper ( root . left , intervals [ 0 ], intervals [ 1 ], c if start <= root_l else root . count ) root . right = self . book_helper ( root . right , intervals [ 2 ], intervals [ 3 ], c if end >= root_r else root . count ) root . count += c self . maxK = max ( root . count , self . maxK ) return root def book ( self , start , end ): """ :type start: int :type end: int :rtype: int """ self . root = self . book_helper ( self . root , start , end , 1 ) return self . maxK # Your MyCalendarThree object will be instantiated and called as such: # obj = MyCalendarThree() # param_1 = obj.book(start,end)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.