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
繼續逃避線段樹......