题目：
Implement aMyCalendarThreeclass to store your events. A new event canalwaysbe 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 numbersxsuch thatstart <= x < end.
AK-bookinghappens whenKevents have some non-empty intersection (ie., there is some time that is common to all K events.)
For each call to the methodMyCalendar.book, return an integerKrepresenting the largest integer such that there exists aK-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 toMyCalendarThree.bookper test case will be at most400.
In calls toMyCalendarThree.book(start, end),startandendare integers in the range[0, 10^9].
题解：
Maintain the ongoing events by plus one at each booking start and minus one at each booling end.
Accumlate ongoing events count and return the maximum.
It could array to maintain such events, but input may be sparse. Thus it would be better to use TreeMap.
Time Complexity: book, O(nlogn). n is size of tm.
Space: O(n).
AC Java:
1 classMyCalendarThree {2 TreeMaptm;3
4 publicMyCalendarThree() {5 tm = new TreeMap<>();6 }7
8 public int book(int start, intend) {9 tm.put(start, tm.getOrDefault(start, 0)+1);10 tm.put(end, tm.getOrDefault(end, 0)-1);11
12 int res = 0;13 int ongoing = 0;14 for(intcount : tm.values()){15 ongoing +=count;16 res =Math.max(res, ongoing);17 }18
19 returnres;20 }21 }22
23 /**
24 * Your MyCalendarThree object will be instantiated and called as such:25 * MyCalendarThree obj = new MyCalendarThree();26 * int param_1 = obj.book(start,end);27 */
如果觉得《java732_LeetCode 732. My Calendar III》对你有帮助，请点赞、收藏，并留下你的观点哦！
