732. My Calendar III
给你很多事件和他们发生的时段 问你最多同时发生的事件数 k 是多少
每加入一个新事件都要纪录一次 k
Example 1:
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
思路:
解1. 纪录事件点然后 sweep line 扫一次 状态变化只发生在开始和结束
总之就是对每个事件塞 (start, 1) 和 (end, -1) 进 sortedlist 里
然后对 x[0] 从小到大扫一次 算出最大值
每次 book 都要重扫一次所有事件点 时间复杂度O(n^2)...这样也能过?
from sortedcontainers import SortedList
class MyCalendarThree:
def __init__(self):
self.events = SortedList()
def book(self, start: int, end: int) -> int:
self.events.add((start, 1))
self.events.add((end, -1))
res = cur = 0
for event in self.events:
cur += event[1]
res = max(res, cur)
return res
解2. 改良法一 把每个事件点的事件数存在 dict 里
在 book 新的 start 和 end 的时候 只更新他们中间的事件点
这样就可以不用每次都扫全部的事件点
最差一样是O(n^2) 如果每次更新的 start 和 end 都包住全部的事件点的话
class MyCalendarThree:
def __init__(self):
self.books = dict([(-1, 0), (10**9+1, 0)])
self.events = [-1, 10**9+1]
self.k = 0
def book(self, start: int, end: int) -> int:
left = bisect_left(self.events, start)
if self.events[left] != start:
self.events.insert(left, start)
self.books[start] = self.books[self.events[left-1]]
right = bisect_left(self.events, end)
if self.events[right] != end:
self.events.insert(right, end)
self.books[end] = self.books[self.events[right-1]]
for i in range(left, right):
self.books[self.events[i]] += 1
self.k = max(self.k, self.books[self.events[i]])
return self.k
继续逃避线段树......