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; } } }
-
// 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 ans = 0 activeEvents = 0 for count in self.timeline.values(): activeEvents += count ans = max(ans, activeEvents) return ans ############ 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)