LeetCode 0732. My Calendar III Solution in Java, C++, Python & More | Explanation + Code

Description

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 integer k representing the largest integer such that there exists a k-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 400 calls will be made to book.

Solutions

Solution 1: Segment Tree

A segment tree divides the entire interval into multiple non-contiguous subintervals, with the number of subintervals not exceeding log(width). To update the value of an element, we only need to update log(width) intervals, and these intervals are all contained within a larger interval that includes the element. When modifying intervals, we use lazy propagation to ensure efficiency.

• Each node of the segment tree represents an interval.
• The segment tree has a unique root node representing the entire range, such as [1, N].
• Each leaf node of the segment tree represents a unit interval of length 1, [x, x].
• For each internal node [l, r], its left child is [l, mid] and its right child is [mid + 1, r], where mid = \lfloor(l + r) / 2\rfloor (i.e., floor division).

For this problem, the segment tree nodes maintain the following information:

1. The maximum number of times the interval has been booked, v.
2. Lazy propagation marker, add.

Since the time range is 10^9, which is very large, we use dynamic node creation.

The time complexity is O(n × log n), and the space complexity is O(n), where n is the number of bookings.

PythonJavaC++GoTypeScript

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: int, r: int, v: int, node: 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: int, r: int, node: Node = None) -> int: 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): node.v = max(node.left.v, node.right.v) def pushdown(self, node: 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)(code-box)

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) 1e9 + 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) 1e9 + 1); } } /** * Your MyCalendarThree object will be instantiated and called as such: * MyCalendarThree obj = new MyCalendarThree(); * int param_1 = obj.book(start,end); */(code-box)

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); */(code-box)

type node struct { left *node right *node l, mid, r int v, add int } func newNode(l, r int) *node { return &node{ l: l, r: r, mid: int(uint(l+r) >> 1), } } type segmentTree struct { root *node } func newSegmentTree() *segmentTree { return &segmentTree{ root: newNode(1, 1e9+1), } } func (t *segmentTree) modify(l, r, v int, n *node) { if l > r { return } if n.l >= l && n.r <= r { n.v += v n.add += v return } t.pushdown(n) if l <= n.mid { t.modify(l, r, v, n.left) } if r > n.mid { t.modify(l, r, v, n.right) } t.pushup(n) } func (t *segmentTree) query(l, r int, n *node) int { if l > r { return 0 } if n.l >= l && n.r <= r { return n.v } t.pushdown(n) v := 0 if l <= n.mid { v = max(v, t.query(l, r, n.left)) } if r > n.mid { v = max(v, t.query(l, r, n.right)) } return v } func (t *segmentTree) pushup(n *node) { n.v = max(n.left.v, n.right.v) } func (t *segmentTree) pushdown(n *node) { if n.left == nil { n.left = newNode(n.l, n.mid) } if n.right == nil { n.right = newNode(n.mid+1, n.r) } if n.add != 0 { n.left.add += n.add n.right.add += n.add n.left.v += n.add n.right.v += n.add n.add = 0 } } type MyCalendarThree struct { tree *segmentTree } func Constructor() MyCalendarThree { return MyCalendarThree{newSegmentTree()} } func (this *MyCalendarThree) Book(start int, end int) int { this.tree.modify(start+1, end, 1, this.tree.root) return this.tree.query(1, int(1e9)+1, this.tree.root) } /** * Your MyCalendarThree object will be instantiated and called as such: * obj := Constructor(); * param_1 := obj.Book(start,end); */(code-box)

class Node { left: Node | null = null; right: Node | null = null; l: number; r: number; mid: number; v: number = 0; add: number = 0; constructor(l: number, r: number) { this.l = l; this.r = r; this.mid = (l + r) >> 1; } } class SegmentTree { private root: Node = new Node(1, 1e9 + 1); constructor() {} modify(l: number, r: number, v: number, node: Node = this.root): void { if (l > r) { return; } if (node.l >= l && node.r <= r) { node.v += v; node.add += v; return; } this.pushdown(node); if (l <= node.mid) { this.modify(l, r, v, node.left!); } if (r > node.mid) { this.modify(l, r, v, node.right!); } this.pushup(node); } query(l: number, r: number, node: Node = this.root): number { if (l > r) { return 0; } if (node.l >= l && node.r <= r) { return node.v; } this.pushdown(node); let v = 0; if (l <= node.mid) { v = Math.max(v, this.query(l, r, node.left!)); } if (r > node.mid) { v = Math.max(v, this.query(l, r, node.right!)); } return v; } private pushup(node: Node): void { node.v = Math.max(node.left!.v, node.right!.v); } private pushdown(node: Node): void { 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) { const left = node.left!; const 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 tree: SegmentTree; constructor() { this.tree = new SegmentTree(); } book(start: number, end: number): number { this.tree.modify(start + 1, end, 1); return this.tree.query(1, 1e9 + 1); } } /** * Your MyCalendarThree object will be instantiated and called as such: * var obj = new MyCalendarThree() * var param_1 = obj.book(startTime, endTime) */(code-box)