lc731. 我的日程安排表 ii

题目链接：

题解

LC729. 我的日程安排表 I、LC731. 我的日程安排表 II、LC732. 我的日程安排表 III 三题基本差不多。由于先写的 732，当时写了线段树，所以这三题都用线段树写了。标准区间查询和区间修改题目。

参考代码

class MyCalendarTwo:

    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 check(self, start: int, end: int, l: int, r: int, idx: int):
        if r < start or end < l:
            return 0
        if start <= l and r <= end:
            return self.tree[idx] 
        else:
            mid = (l+r) //2
            return self.lazy[idx] + max(self.check(start, end, l, mid, idx*2), self.check(start, end, mid + 1, r, idx*2+1))

    def book(self, startTime: int, endTime: int) -> bool:
        ret = self.check(startTime, endTime - 1, 0, 10 ** 9, 1)
        # print(startTime, endTime, ret)
        if ret >= 2:
            return False
        else:
            self.update(startTime, endTime - 1, 0, 10 ** 9, 1)
            return True