732 我的日程安排表 III（差分思想）-蒲公英云

732 我的日程安排表 III（差分思想）

1. 问题描述：

当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。
MyCalendarThree() 初始化对象。
int book(int start, int end) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。

示例：

输入：

[“MyCalendarThree”, “book”, “book”, “book”, “book”, “book”, “book”]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

输出：

[null, 1, 1, 2, 3, 3, 3]

解释：

MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ，剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

提示：

0 <= start < end <= 10 ^ 9
每个测试用例，调用 book 函数最多不超过 400次
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/my-calendar-iii

2. 思路分析：

分析题目可以知道这道题目类似于力扣的699题，因为涉及到区间修改与区间查询操作，所以可以使用带有懒标记的线段树进行求解（区间所有元素整体加1），但是带有懒标记的线段树比较复杂而且耗时比较大（c++不容易超时但是java等语言很容易超时），因为涉及到区间整体加1（差分可以解决区间整体加上某个数的题目）所以我们可以借助于差分的思想，每一次添加一个区间的时候可以使用一个数据结构来维护区间的左端点加1，右端点减1，因为在插入区间的时候需要维护区间的有序性，c++可以使用map来维护，python可以使用sortedcontainers.SortedDict()来维护，这样我们在插入元素的时候就可以维护插入当前区间之后还是有序的。

3. 代码如下：

python（使用排序容器SortedDict来维持插入的元素是有序的）：

import sortedcontainers
class MyCalendarThree:
    def __init__(self):
        # 维护插入的区间是有序的
        self.S = sortedcontainers.SortedDict()  # 差分
    def book(self, start: int, end: int) -> int:
        if start not in self.S:
            self.S[start] = 0
        self.S[start] += 1
        if end not in self.S:
            self.S[end] = 0
        self.S[end] -= 1
        res = 0
        s = 0
        for k, v in self.S.items():
            s += v
            res = max(res, s)
        return res