732. My Calendar III

HardDesignSegment TreeBinary SearchOrdered Set
Leetcode Link

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:

  1. We use the modify function to increment the overlap count for every relevant segment in the tree that the event passes through.
  2. While making updates, we apply a "lazy propagation" strategy (pushdown method) to avoid unnecessary updates until required, which helps to keep the operation efficient.
  3. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

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 calls pushdown 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 as modify 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 the add 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 maximum k (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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

Example 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.

  1. The MyCalendarThree class is initialized, and an instance of SegmentTree is created. The segment tree's root node covers the entire possible booking range.

  2. 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 only 1.

  3. 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 now 2, representing the overlap between the first and second bookings.

  4. 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 returns 2 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
Not Sure What to Study? Take the 2-min Quiz：

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

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:

  1. Modification (Adding a Booking): Each call to modify results in at most O(logN) recursive calls since we are diving the segment into two halves at each level, where N 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 to modify might have to create nodes if the segments are not already present, so the worst-case time complexity for a single book operation which calls modify is O(logN).

  2. Query (Retrieving the Maximum Booking Count): Each call to query function follows the same logic and complexity as the modify function. Hence, its time complexity is also O(logN) for the range [1, 10^9]. However, when calling query from the book method, since we're querying the entire range, the complexity still remains O(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:

  1. 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 distinct book operations, the tree could become very large. However, since nodes are created on demand, the total number of nodes will be O(M * logN), where M is the number of distinct bookings made. Note that M could be much smaller than N.

  2. 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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these pictures shows the visit order of a depth-first search?

Recommended Readings

Segment Tree

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

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫