My Calendar III Problem
Description
LeetCode Problem 732.
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 [start, end), 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 start, int end) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.
Example 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
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, The first event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarThree.book(50, 60); // return 1, The second event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarThree.book(10, 40); // return 2, The third event [10, 40) intersects the first event, and the maximum k-booking is a 2-booking.
myCalendarThree.book(5, 15); // return 3, The remaining events cause the maximum K-booking to be only a 3-booking.
myCalendarThree.book(5, 10); // return 3
myCalendarThree.book(25, 55); // return 3
Constraints:
- 0 <= start < end <= 10^9
- At most 400 calls will be made to book.
Sample C++ Code
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
class MyCalendarThree {
int maxCnt = 0;
// key: time; val: +1 if start, -1 if end
map<int, int> mp;
public:
MyCalendarThree() {
}
int book (int start, int end) {
mp[start] ++;
mp[end] --;
int cnt = 0;
for (auto it = mp.begin(); it != mp.end(); it++) {
cnt += it->second;
maxCnt = max(cnt, maxCnt);
}
return maxCnt;
}
};
/**
* Your MyCalendarThree object will be instantiated and called as such:
* MyCalendarThree* obj = new MyCalendarThree();
* int param_1 = obj->book(start,end);
*/