1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class MyCalendarThree:
def __init__(self):
self.tree = defaultdict(int)
self.lazy = defaultdict(int)
def update(self, start: int, end: int, l: int, r: int, idx: int):
if r < start or end < l:
return
if start <= l and r <= end:
self.tree[idx] += 1
self.lazy[idx] += 1
else:
mid = (l + r) // 2
self.update(start, end, l, mid, idx * 2)
self.update(start, end, mid + 1, r, idx * 2 + 1)
self.tree[idx] = self.lazy[idx] + max(self.tree[idx * 2], self.tree[idx * 2 + 1])
def book(self, start: int, end: int) -> int:
self.update(start, end - 1, 0, 10 ** 9, 1)
return self.tree[1]
|