Problem:
link:Ā https://leetcode.com/problems/my-calendar-iii/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 mostĀ400. - In calls toĀ
MyCalendarThree.book(start, end),ĀstartĀ andĀendĀ are integers in the rangeĀ[0, 10^9].
Idea:
Similar to LeetCode 731Ā My Calendar II Use an ordered / tree map to track the number of event at current time.
For a new book event, increase the number of events at start, decrease the number of events at end.
Scan the timeline to find the maximum number of events.
Ā
Solution 1: Count Boundaries
Time complexity: O(n^2)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua // Runtime: 116 ms class MyCalendarThree { public: MyCalendarThree() {} int book(int start, int end) { ++deltas_[start]; --deltas_[end]; int ans = 0; int curr = 0; for (const auto& kv : deltas_) ans = max(ans, curr += kv.second); return ans; } private: map<int, int> deltas_; }; |
Solution 2
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
// Author: Huahua // Runtime: 66 ms class MyCalendarThree { public: MyCalendarThree() { counts_[INT_MIN] = 0; counts_[INT_MAX] = 0; max_count_ = 0; } int book(int start, int end) { auto l = prev(counts_.upper_bound(start)); // l->first < start auto r = counts_.lower_bound(end); // r->first >= end for (auto curr = l, next = curr; curr != r; curr = next) { ++next; if (next->first > end) counts_[end] = curr->second; if (curr->first <= start && next->first > start) max_count_ = max(max_count_, counts_[start] = curr->second + 1); else max_count_ = max(max_count_, ++curr->second); } return max_count_; } private: map<int, int> counts_; int max_count_; }; |
Solution 3:Ā Segment Tree
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
// Author: Huahua // Runtime: 63 ms (<95.65%) class MyCalendarThree { public: MyCalendarThree(): max_count_(0) { root_.reset(new Node(0, 100000000, 0)); } int book(int start, int end) { Add(start, end, root_.get()); return max_count_; } private: struct Node { Node(int l, int r, int count):l(l), m(-1), r(r), count(count){} int l; int m; int r; int count; std::unique_ptr<Node> left; std::unique_ptr<Node> right; }; void Add(int start, int end, Node* root) { if (root->m != -1) { if (end <= root->m) Add(start, end, root->left.get()); else if(start >= root->m) Add(start, end, root->right.get()); else { Add(start, root->m, root->left.get()); Add(root->m, end, root->right.get()); } return; } if (start == root->l && end == root->r) max_count_ = max(max_count_, ++root->count); else if (start == root->l) { root->m = end; root->left.reset(new Node(start, root->m, root->count + 1)); root->right.reset(new Node(root->m, root->r, root->count)); max_count_ = max(max_count_, root->count + 1); } else if(end == root->r) { root->m = start; root->left.reset(new Node(root->l, root->m, root->count)); root->right.reset(new Node(root->m, root->r, root->count + 1)); max_count_ = max(max_count_, root->count + 1); } else { root->m = start; root->left.reset(new Node(root->l, root->m, root->count)); root->right.reset(new Node(root->m, root->r, root->count)); Add(start, end, root->right.get()); } } std::unique_ptr<Node> root_; int max_count_; }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
""" Author: Huahua Runtime: 436 ms (<88.88%) """ class Node: def __init__(self, l, r, count): self.l = l self.m = -1 self.r = r self.count = count self.left = None self.right = None class MyCalendarThree: def __init__(self): self.root = Node(0, 10**9, 0) self.max = 0 def book(self, start, end): self.add(start, end, self.root) return self.max def add(self, start, end, root): if root.m != -1: if end <= root.m: self.add(start, end, root.left) elif start >= root.m: self.add(start, end, root.right) else: self.add(start, root.m, root.left) self.add(root.m, end, root.right) return if start == root.l and end == root.r: root.count += 1 self.max = max(self.max, root.count) elif start == root.l: root.m = end root.left = Node(start, root.m, root.count + 1) root.right = Node(root.m, root.r, root.count) self.max = max(self.max, root.count + 1) elif end == root.r: root.m = start; root.left = Node(root.l, root.m, root.count) root.right = Node(root.m, root.r, root.count + 1) self.max = max(self.max, root.count + 1) else: root.m = start root.left = Node(root.l, root.m, root.count) root.right = Node(root.m, root.r, root.count) self.add(start, end, root.right) |
Related Problems: