732. My Calendar III
Problem Description
In this problem, we are asked to implement a class MyCalendarThree
which simulates a calendar that can track events and determine the maximum number of concurrent events at any given time. A k-booking means that k events overlap at some point. The book
method will be called multiple times, each time with a startTime
and an endTime
of a new event (startTime, endTime)
, and it should return the maximum number of concurrent or overlapping events (k
) that have been booked so far.
The core challenge comes from the fact that the number of book
method calls can be quite large and that we must keep track of the maximum number of overlapping intervals efficiently after each call.
Intuition
To address the problem efficiently, the solution leverages a data structure known as a segment tree. Segment trees are ideal for scenarios where we frequently perform range-based queries and modifications to an array or, in this case, ranges of time.
The intuition behind using a segment tree for this problem comes from the fact that we can treat each booking as an increment operation over a range of time. When we book a new event, we increase the overlapping count for that time interval.
The Segment Tree is built with methods for modifying (adding a booking) and querying (checking the maximum number of bookings) over a range. It is initialized to cover the entire range of possible bookings (from 1 to 10^9, as given in the Node initial range). Each node in the tree represents a range of time with the range's left boundary (l
), right boundary (r
), and the maximum bookings (v
) in that range.
When a new booking is made:
- We use the
modify
function to increment the overlap count for every relevant segment in the tree that the event passes through. - While making updates, we apply a "lazy propagation" strategy (pushdown method) to avoid unnecessary updates until required, which helps to keep the operation efficient.
- After modifying the tree, we use the
query
function to find the maximum overlap (k) by examining the relevant segments of the tree.
By the end of the book
method call, we have the updated segment tree reflecting all the bookings and can return the overall maximum overlap. This method allows us to maintain and query the bookings in logarithmic time complexity in relation to the depth of the segment tree, which is much faster than simple linear checking of all the intervals.
Learn more about Segment Tree and Binary Search patterns.
Solution Approach
The solution approach entails a few essential components: a dynamic segment tree structure, lazy propagation for efficient updates, and methods to modify and query the tree. Below is a step-by-step breakdown of each part of the implementation:
Node Class
The Node
class represents each node in the segment tree. Each node has potential children (left
, right
), boundaries for the segment it represents (l
, r
), a midpoint (mid
) for splitting the segment, a value (v
) to store the number of bookings in the segment, and an additional value (add
) that helps in lazy updates.
SegmentTree Class
Here, we define the segment tree itself with a root node covering the entire range of possible values. The class includes functions that operate on the tree:
-
modify(l, r, v, node): This recursive function is called whenever a booking is made. It increments the booking count in each relevant segment by
v
. If the entire segment lies within the booking interval, it updates the node's value and the lazy value (used for propagation). If only parts of the node's segment are affected, it callspushdown
to ensure children nodes are created and/or updated, and then recurses into them. -
query(l, r, node): This function finds the maximum booking count in the range
[l, r]
. It uses the same segment-matching logic asmodify
to drill down into the tree. When a node is fully within the range, its value is used directly. Otherwise, the function recurses into relevant children nodes and takes the maximum value found. -
pushup(node): This is a helper function to update a node's value based on its children's values.
-
pushdown(node): Before further recursions or queries into child nodes,
pushdown
propagates theadd
value of a node to its children nodes (performing actual updates on them), which is key to the lazy update mechanism. This ensures updates are made only when they are necessary.
MyCalendarThree Class
This class uses an instance of SegmentTree
.
-
init(): Initializes a new
SegmentTree
. -
book(start, end): Public method called to book an event. It modifies the tree by incrementing the booking count in the range
[start + 1, end]
because we are using 1-based indices. Then it queries the entire range of possible bookings to find and return the maximumk
(booking count).
By utilizing these methods and the dynamic, lazy segment tree, the MyCalendarThree
class can efficiently track the maximum booking overlap after each event is booked.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a simple example:
Suppose we make three booking calls with the following intervals: (10, 20), (15, 25), and (20, 30). We will walk through how the algorithm handles these bookings.
-
The
MyCalendarThree
class is initialized, and an instance ofSegmentTree
is created. The segment tree's root node covers the entire possible booking range. -
The first booking is made with the
book
call:book(10, 20)
.modify
is called on the segment tree with the range[10, 20)
.- Since this is the first booking, the segment tree nodes that represent this range are incremented by 1, and the lazy propagation mechanism ensures that this update is done efficiently.
- The
query
function is then called to find the maximum booking so far, which, in this case, is only1
.
-
The second booking is made with the call:
book(15, 25)
.- The
modify
function is called for the range[15, 25)
. - The segment tree is updated to reflect this booking. Since the range
[15, 20)
overlaps with the first booking, the relevant nodes will have their count incremented accordingly. - Lazy propagation ensures that these updates are made only where necessary and propagate accurately to child nodes.
- A
query
returns that the maximum booking is now2
, representing the overlap between the first and second bookings.
- The
-
Lastly, we call
book(20, 30)
.modify
updates the segment tree for the range[20, 30)
.- This time, there is no overlap with the previous bookings, so it only affects the counts for the relevant time segment from
[20, 30)
. - A
query
still returns2
since there is no change to the maximum booking overlap—it remains at the intersection of the first two bookings.
At the end of these bookings, MyCalendarThree
can answer that the maximum number of concurrent events (k
) is 2
, meaning that at some point, there were two events happening at the same time. The implementation of the segment tree, particularly the lazy propagation, allowed us to efficiently manage and query the overlaps even as more bookings were added.
Solution Implementation
1class Node:
2 def __init__(self, left_bound, right_bound):
3 # Initialize a segment tree node representing the interval [left_bound, right_bound]
4 self.left_child = None
5 self.right_child = None
6 self.left_bound = left_bound
7 self.right_bound = right_bound
8 self.mid = (left_bound + right_bound) >> 1 # Integer division by two
9 self.value = 0 # The value stored at the node
10 self.lazy = 0 # Lazy propagation value for range updates
11
12class SegmentTree:
13 def __init__(self):
14 # Initialize the root node with the entire range from 1 to 1e9 + 1
15 self.root = Node(1, int(1e9 + 1))
16
17 def modify(self, left, right, value, node=None):
18 # Add value to all numbers in the range [left, right] of the segment tree
19 if left > right:
20 return
21 if node is None:
22 node = self.root
23 if node.left_bound >= left and node.right_bound <= right:
24 node.value += value
25 node.lazy += value
26 return
27 self.push_down(node)
28 if left <= node.mid:
29 self.modify(left, right, value, node.left_child)
30 if right > node.mid:
31 self.modify(left, right, value, node.right_child)
32 self.push_up(node)
33
34 def query(self, left, right, node=None):
35 # Find the maximum value in the range [left, right]
36 if left > right:
37 return 0
38 if node is None:
39 node = self.root
40 if node.left_bound >= left and node.right_bound <= right:
41 return node.value
42 self.push_down(node)
43 max_value = 0
44 if left <= node.mid:
45 max_value = max(max_value, self.query(left, right, node.left_child))
46 if right > node.mid:
47 max_value = max(max_value, self.query(left, right, node.right_child))
48 return max_value
49
50 def push_up(self, node):
51 # Update the current node's value based on its children's values
52 node.value = max(node.left_child.value, node.right_child.value)
53
54 def push_down(self, node):
55 # Propagate the lazy updates to the node's children
56 if node.left_child is None:
57 node.left_child = Node(node.left_bound, node.mid)
58 if node.right_child is None:
59 node.right_child = Node(node.mid + 1, node.right_bound)
60 if node.lazy:
61 node.left_child.value += node.lazy
62 node.right_child.value += node.lazy
63 node.left_child.lazy += node.lazy
64 node.right_child.lazy += node.lazy
65 node.lazy = 0
66
67class MyCalendarThree:
68 def __init__(self):
69 # Initialize the segment tree
70 self.tree = SegmentTree()
71
72 def book(self, start: int, end: int) -> int:
73 # Book an event from `start` to `end` and return the maximum number of concurrent events
74 self.tree.modify(start + 1, end, 1) # Segment tree is 1-indexed
75 return self.tree.query(1, int(1e9 + 1)) # Query the entire range for the maximum
76
77
78# Your MyCalendarThree object will be instantiated and called as such:
79# obj = MyCalendarThree()
80# param_1 = obj.book(start, end)
81
1class Node {
2 Node left; // left child in the segment tree
3 Node right; // right child in the segment tree
4 int start; // start of the range
5 int end; // end of the range
6 int mid; // mid-point of the range
7 int value; // value of the node, carrying additional information (e.g., count of events)
8 int lazy; // lazy propagation value to apply to children
9
10 // Constructor for creating a new Node with a given range
11 public Node(int start, int end) {
12 this.start = start;
13 this.end = end;
14 this.mid = (start + end) >> 1; // equivalent to (start + end) / 2
15 }
16}
17
18class SegmentTree {
19 // Class representing a segment tree with lazy propagation
20 private Node root = new Node(1, (int) 1e9 + 1); // create a root node for the segment tree
21
22 // Empty constructor for SegmentTree
23 public SegmentTree() {
24 }
25
26 // Public method to add a value over a specified range
27 public void modify(int start, int end, int value) {
28 modify(start, end, value, root);
29 }
30
31 // Helper method to recursively add a value over a specified range
32 private void modify(int start, int end, int value, Node node) {
33 if (start > end) {
34 return; // invalid range, return early
35 }
36 if (node.start >= start && node.end <= end) {
37 // Current segment is fully covered by [start, end]
38 node.value += value;
39 node.lazy += value; // Set lazy value for further propagation
40 return;
41 }
42 pushdown(node); // Propagate lazy values
43 if (start <= node.mid) {
44 modify(start, end, value, node.left); // Modify left child
45 }
46 if (end > node.mid) {
47 modify(start, end, value, node.right); // Modify right child
48 }
49 pushup(node); // Update current node based on children
50 }
51
52 // Public method to query the maximum value over a specified range
53 public int query(int start, int end) {
54 return query(start, end, root);
55 }
56
57 // Helper method to get the maximum value over a specified range
58 private int query(int start, int end, Node node) {
59 if (start > end) {
60 return 0; // invalid range, return early
61 }
62 if (node.start >= start && node.end <= end) {
63 // Current segment is fully covered by [start, end]
64 return node.value;
65 }
66 pushdown(node); // Propagate lazy values
67 int maxVal = 0;
68 if (start <= node.mid) {
69 maxVal = Math.max(maxVal, query(start, end, node.left)); // Query left child
70 }
71 if (end > node.mid) {
72 maxVal = Math.max(maxVal, query(start, end, node.right)); // Query right child
73 }
74 return maxVal;
75 }
76
77 // Method to update the node's value based on its children's values
78 private void pushup(Node node) {
79 node.value = Math.max(node.left.value, node.right.value);
80 }
81
82 // Method to propagate lazy values to the node's children
83 private void pushdown(Node node) {
84 // Initialize children if necessary
85 if (node.left == null) {
86 node.left = new Node(node.start, node.mid);
87 }
88 if (node.right == null) {
89 node.right = new Node(node.mid + 1, node.end);
90 }
91 // Propagate lazy values to children if any
92 if (node.lazy != 0) {
93 Node left = node.left, right = node.right;
94 left.lazy += node.lazy;
95 right.lazy += node.lazy;
96 left.value += node.lazy;
97 right.value += node.lazy;
98 node.lazy = 0; // Reset lazy value after propagation
99 }
100 }
101}
102
103class MyCalendarThree {
104 // Class representing a calendar that tracks the maximum number of simultaneous events
105 private SegmentTree tree = new SegmentTree();
106
107 // Empty constructor for MyCalendarThree
108 public MyCalendarThree() {
109 }
110
111 // Public method to book an event and get the maximum number of simultaneous events
112 public int book(int start, int end) {
113 tree.modify(start + 1, end, 1); // Add event to the segment tree
114 return tree.query(1, (int) 1e9 + 1); // Query the entire range for the maximum
115 }
116}
117
118// Example of how to use the MyCalendarThree class:
119// MyCalendarThree obj = new MyCalendarThree();
120// int param_1 = obj.book(start, end);
121
1#include <algorithm> // Include algorithm library for max function
2
3// Node represents each node in the Segment Tree
4class Node {
5public:
6 Node* left; // Pointer to the left child
7 Node* right; // Pointer to the right child
8 int start;
9 int end;
10 int mid;
11 int value;
12 int lazy;
13
14 // Constructor initializing the node with the interval [start, end]
15 Node(int start, int end) {
16 this->start = start;
17 this->end = end;
18 this->mid = (start + end) >> 1; // Equivalent to (start+end)/2 but faster
19 this->left = this->right = nullptr;
20 value = lazy = 0;
21 }
22};
23
24// SegmentTree class for handling interval updates and queries
25class SegmentTree {
26private:
27 Node* root;
28
29public:
30 // Constructor initializes the tree with a root node covering the range [1, 1e9 + 1]
31 SegmentTree() {
32 root = new Node(1, static_cast<int>(1e9) + 1);
33 }
34
35 // Method to perform range update
36 void modify(int start, int end, int value) {
37 modify(start, end, value, root);
38 }
39
40 // Private method to perform range update on a specific node
41 void modify(int start, int end, int value, Node* node) {
42 if (start > end)
43 return;
44 if (node->start >= start && node->end <= end) { // Current segment is fully within the update range
45 node->value += value; // Update the value at the current node
46 node->lazy += value; // Mark the current node as lazy
47 return;
48 }
49 pushdown(node); // Push the lazy update to the children
50 // Recur to the children nodes
51 if (start <= node->mid)
52 modify(start, end, value, node->left);
53 if (end > node->mid)
54 modify(start, end, value, node->right);
55 pushup(node); // Update the current node using the children's values
56 }
57
58 // Method to perform range query
59 int query(int start, int end) {
60 return query(start, end, root);
61 }
62
63 // Private method to query the value on a specific range
64 int query(int start, int end, Node* node) {
65 if (start > end)
66 return 0;
67 if (node->start >= start && node->end <= end) // Current segment is fully within the query range
68 return node->value;
69 pushdown(node); // Apply any pending updates
70 int maxValue = 0;
71 // Recur to the children nodes
72 if (start <= node->mid)
73 maxValue = std::max(maxValue, query(start, end, node->left));
74 if (end > node->mid)
75 maxValue = std::max(maxValue, query(start, end, node->right));
76 return maxValue; // Return the max value found in the range
77 }
78
79 // Update the current node's value based on its children
80 void pushup(Node* node) {
81 node->value = std::max(node->left->value, node->right->value);
82 }
83
84 // Propagate lazy updates to the children
85 void pushdown(Node* node) {
86 if (!node->left) node->left = new Node(node->start, node->mid);
87 if (!node->right) node->right = new Node(node->mid + 1, node->end);
88 if (node->lazy) { // If the current node has a lazy value
89 // Propagate the lazy value to both children
90 node->left->value += node->lazy;
91 node->left->lazy += node->lazy;
92 node->right->value += node->lazy;
93 node->right->lazy += node->lazy;
94 // Reset the lazy value for the current node
95 node->lazy = 0;
96 }
97 }
98};
99
100// MyCalendarThree class to keep track of the number of events at any point in time
101class MyCalendarThree {
102public:
103 SegmentTree* tree;
104
105 // Constructor initializing the MyCalendarThree with a Segment Tree
106 MyCalendarThree() {
107 tree = new SegmentTree();
108 }
109
110 // Method to book an event and return the maximum number of overlapping events
111 int book(int start, int end) {
112 // Increase the count for the range [start + 1, end]
113 tree->modify(start + 1, end, 1);
114 // Query the entire range to find the maximum number of overlapping events
115 return tree->query(1, static_cast<int>(1e9) + 1);
116 }
117};
118
119/**
120 * Your MyCalendarThree object will be instantiated and called as such:
121 * MyCalendarThree* obj = new MyCalendarThree();
122 * int param_1 = obj->book(start,end);
123 */
124
1// TypeScript uses classes, and moving logic to a global scope (outside of a class) is not recommended for this use case.
2// Instead, we are only removing the explicit class definitions, but keeping a class-like structure for better encapsulation and organization.
3
4// Include 'max' operation from Math object
5
6// Node represents each node in the Segment Tree
7interface Node {
8 left: Node | null;
9 right: Node | null;
10 start: number;
11 end: number;
12 mid: number;
13 value: number;
14 lazy: number;
15}
16
17function createNode(start: number, end: number): Node {
18 return {
19 start: start,
20 end: end,
21 mid: (start + end) >> 1,
22 left: null,
23 right: null,
24 value: 0,
25 lazy: 0,
26 };
27}
28
29// A root node covering the range [1, 1e9 + 1]
30let root = createNode(1, 1e9 + 1);
31
32// Function to perform range update
33function modify(start: number, end: number, value: number, node: Node = root) {
34 if (start > end) return;
35
36 if (node.start >= start && node.end <= end) {
37 node.value += value;
38 node.lazy += value;
39 return;
40 }
41
42 pushdown(node);
43
44 if (start <= node.mid) modify(start, end, value, node.left!);
45 if (end > node.mid) modify(start, end, value, node.right!);
46
47 pushup(node);
48}
49
50// Function to perform range query
51function query(start: number, end: number, node: Node = root): number {
52 if (start > end) return 0;
53
54 if (node.start >= start && node.end <= end) return node.value;
55
56 pushdown(node);
57
58 let maxValue = 0;
59 if (start <= node.mid) maxValue = Math.max(maxValue, query(start, end, node.left!));
60 if (end > node.mid) maxValue = Math.max(maxValue, query(start, end, node.right!));
61
62 return maxValue;
63}
64
65// Update the current node's value based on its children
66function pushup(node: Node) {
67 if (node.left && node.right) {
68 node.value = Math.max(node.left.value, node.right.value);
69 }
70}
71
72// Propagate lazy updates to the children
73function pushdown(node: Node) {
74 if (!node.left) node.left = createNode(node.start, node.mid);
75 if (!node.right) node.right = createNode(node.mid + 1, node.end);
76
77 if (node.lazy) {
78 node.left.value += node.lazy;
79 node.left.lazy += node.lazy;
80
81 node.right.value += node.lazy;
82 node.right.lazy += node.lazy;
83
84 node.lazy = 0;
85 }
86}
87
88// Object to keep track of the number of events at any point in time using a Segment Tree
89let myCalendarThree = {
90 tree: {
91 root: root,
92 modify: modify,
93 query: query,
94 },
95
96 // Method to book an event and return the maximum number of overlapping events
97 book(start: number, end: number): number {
98 this.tree.modify(start + 1, end, 1);
99 return this.tree.query(1, 1e9 + 1);
100 },
101};
102
Time and Space Complexity
The given code implements a segment tree to solve the problem of finding the maximum number of concurrent events (bookings) in a calendar.
Time Complexity:
-
Modification (Adding a Booking): Each call to
modify
results in at mostO(logN)
recursive calls since we are diving the segment into two halves at each level, whereN
is the range of the coordinates (in this case,[1, 10^9]
). However, because the segment tree is lazy and nodes are created on-demand, the actual height of the tree depends on the number of distinct ranges that have been added. Every call tomodify
might have to create nodes if the segments are not already present, so the worst-case time complexity for a singlebook
operation which callsmodify
isO(logN)
. -
Query (Retrieving the Maximum Booking Count): Each call to
query
function follows the same logic and complexity as themodify
function. Hence, its time complexity is alsoO(logN)
for the range[1, 10^9]
. However, when callingquery
from thebook
method, since we're querying the entire range, the complexity still remainsO(logN)
since it has to traverse from the root to the leaves.
Therefore, the overall time complexity for a single book
call is O(logN)
.
Space Complexity:
-
Segment Tree Nodes: The space complexity is dependent on the number of unique segments created and is hence proportional to the number of times
modify
operations create new nodes. In the worst-case scenario, where we have a large number of distinctbook
operations, the tree could become very large. However, since nodes are created on demand, the total number of nodes will beO(M * logN)
, whereM
is the number of distinct bookings made. Note thatM
could be much smaller thanN
. -
Recursion Stack: When considering the space complexity, we also need to account for the call stack during recursive operations. However, since the tree's height is
O(logN)
, the recursion stack will not exceed this height.
In conclusion, the space complexity is O(M * logN)
.
To fill completely from the reference answer, we would need the specifics of the operations encountered, but this is the inherent complexity based on the algorithm's structure and operations.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!