1.题目基本信息

1.1.题目描述

实现一个程序来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。

当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生 三重预订。

事件能够用一对整数 startTime 和 endTime 表示，在一个半开区间的时间 [startTime, endTime) 上预定。实数 x 的范围为 startTime <= x < endTime。

实现 MyCalendarTwo 类：

• MyCalendarTwo() 初始化日历对象。

• boolean book(int startTime, int endTime) 如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

1.2.题目地址

https://leetcode.cn/problems/my-calendar-ii/description/

2.解题方法

2.1.解题思路

思路1：差分数组+有序集合。性质：差分数组的前缀和为原数组

思路2：线段树（维护区间最大值）

3.解题代码

python3代码-差分数组+有序集合

from sortedcontainers import SortedDict

class MyCalendarTwo:
    # 思路1：差分数组+有序集合。性质：差分数组的前缀和为原数组
    def __init__(self):
        self.diffArr = SortedDict()

    def book(self, startTime: int, endTime: int) -> bool:
        self.diffArr[startTime] = self.diffArr.get(startTime, 0) + 1
        self.diffArr[endTime] = self.diffArr.get(endTime, 0) - 1
        sum1 = 0
        for k, v in self.diffArr.items():
            sum1 += v
            if sum1 >= 3:
                self.diffArr[startTime] -= 1
                self.diffArr[endTime] += 1
                return False
        return True


# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(startTime,endTime)

python3代码-线段树

class SegNode():
    def __init__(self, l:int, r:int):
        self.left = None
        self.right = None
        self.l = l
        self.r = r
        self.mid = (r - l) // 2 + l
        self.value = 0  # 维护区间最大值
        self.lazy = 0   # 子树懒增加的值

class SegmentTree():
    def __init__(self, n):
        self.root = SegNode(0, n)
    
    def rangeUpdate(self, start:int, end:int, addValue:int):
        self._rangeUpdate(start, end, addValue, self.root)
    
    def rangeMax(self, start:int, end:int) -> int:
        return self._rangeMax(start, end, self.root)
    
    # > 将「交集区间」的元素值都加1
    def _rangeUpdate(self, start:int, end:int, addValue:int, node:SegNode):
        # > 「交集区间」为空
        if start > end:
            return
        if start > node.r or end < node.l:
            return
        # > 「交集区间」被包含
        if start <= node.l and end >= node.r:
            node.value += addValue
            node.lazy += addValue
            return
        # > 其他情况，递归处理
        self.pushdown(node)
        if start <= node.mid:
            self._rangeUpdate(start, end, addValue, node.left)
        if end > node.mid:
            self._rangeUpdate(start, end, addValue, node.right)
        self.pushup(node)
    
    # > 查询「交集区间」的最大值
    def _rangeMax(self, start:int, end:int, node:SegNode) -> int:
        # > 「交集区间」为空
        if start > end:
            return -inf
        if start > node.r or end < node.l:
            return -inf
        # > 「交集区间」被包含
        if start <= node.l and end >= node.r:
            return node.value
        # > 其他情况，递归处理
        self.pushdown(node)
        ans = -inf
        if start <= node.mid:
            ans = max(ans, self._rangeMax(start, end, node.left))
        if end > node.mid:
            ans = max(ans, self._rangeMax(start, end, node.right))
        return ans

    # > 将子结点的更新信息上浮给父结点
    def pushup(self, node:SegNode):
        node.value = max(node.left.value, node.right.value)
    
    # > 将父结点的懒操作和相关信息下沉给子结点
    def pushdown(self, node:SegNode):
        if node.left is None:
            node.left = SegNode(node.l, node.mid)
        if node.right is None:
            node.right = SegNode(node.mid + 1, node.r)
        if node.lazy != 0:
            node.left.value += node.lazy
            node.right.value += node.lazy
            node.left.lazy += node.lazy
            node.right.lazy += node.lazy
            node.lazy = 0

class MyCalendarTwo:
    # 思路2：线段树（维护区间最大值）
    def __init__(self):
        self.segTree = SegmentTree(1e9)

    def book(self, startTime: int, endTime: int) -> bool:
        self.segTree.rangeUpdate(startTime, endTime - 1, 1)
        maxVal = self.segTree.rangeMax(startTime, endTime - 1)
        if maxVal >= 3:
            self.segTree.rangeUpdate(startTime, endTime - 1, -1)
            return False
        return True

4.执行结果