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]
|