1.题目基本信息

1.1.题目描述

当 k 个日程存在一些非空交集时（即, k 个日程包含了一些相同时间），就会产生 k 次预订。

给你一些日程安排 [startTime, endTime) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

• MyCalendarThree() 初始化对象。

• int book(int startTime, int endTime) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。

1.2.题目地址

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

2.解题方法

2.1.解题思路

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

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

3.解题代码

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

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

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



# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# 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 MyCalendarThree:
    # 思路2：线段树（维护区间最大值）
    def __init__(self):
        self.segTree = SegmentTree(1e9)

    def book(self, startTime: int, endTime: int) -> int:
        self.segTree.rangeUpdate(startTime, endTime - 1, 1)
        return self.segTree.rangeMax(0, 1e9)

4.执行结果