Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/732.html
732. My Calendar III
Level
Hard
Description
Implement a MyCalendarThree
class to store your events. A new event can always be added.
Your class will have one method, book(int start, int end)
. Formally, this represents a booking on the half open interval [start, end)
, the range of real numbers x
such that start <= x < end
.
A K-booking happens when K events have some non-empty intersection (ie., there is some time that is common to all K events.)
For each call to the method MyCalendar.book
, return an integer K
representing the largest integer such that there exists a K-booking in the calendar.
Your class will be called like this: MyCalendarThree cal = new MyCalendarThree();
MyCalendarThree.book(start, end)
Example 1:
MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
Explanation:
The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking.
The third event [10, 40) intersects the first event, and the maximum K-booking is a 2-booking.
The remaining events cause the maximum K-booking to be only a 3-booking.
Note that the last event locally causes a 2-booking, but the answer is still 3 because
eg. [10, 20), [10, 40), and [5, 15) are still triple booked.
Note:
- The number of calls to
MyCalendarThree.book
per test case will be at most400
. - In calls to
MyCalendarThree.book(start, end)
,start
andend
are integers in the range[0, 10^9]
.
Solution
Use TreeMap
, which contains all keys in sorted order. Each time book(int start, int end)
is called, update the values of the keys start
and end
in the map by increasing the value of key start
by 1 and decreasing the value of key end
by 1. Then loop over all the keys in the map to obtain the booking count of each time and the maximum booking, and return the maximum booking.
-
import java.util.TreeMap; public class My_Calendar_III { // ref: https://leetcode.com/articles/my-calendar-iii/ // `start+1` and `end-1` class MyCalendarThree { TreeMap<Integer, Integer> timeCountMap; public MyCalendarThree() { timeCountMap = new TreeMap<>(); } public int book(int start, int end) { timeCountMap.put(start, timeCountMap.getOrDefault(start, 0) + 1); timeCountMap.put(end, timeCountMap.getOrDefault(end, 0) - 1); int active = 0; int result = 0; for (int d : timeCountMap.values()) { active += d; result = Math.max(result, active); } return result; } } } ############ 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); */
-
// OJ: https://leetcode.com/problems/my-calendar-iii/ // Time: // MyCalendarThree: O(1) // book: O(N) // Space: O(N) class MyCalendarThree { map<int, int> m; public: MyCalendarThree() {} int book(int start, int end) { m[start]++; m[end]--; int ans = 1, cur = 0; for (auto &[p, d] : m) { ans = max(ans, cur += d); } return ans; } };
-
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)
-
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), } } func max(x, y int) int { if x > y { return x } return y } 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); */