732. 我的日程安排表 III

题目描述

当 k 个日程安排存在一些非空交集时，就会产生一次 k 次预订。

实现一个 MyCalendarThree 类，来存放你的日程安排，并且在每次成功添加一个新日程安排后，返回当前日历中出现的 最大 k 次预订数。

这题依然使用半开区间 [startTime, endTime)，也就是：

text

startTime <= x < endTime

实现 MyCalendarThree 类：

MyCalendarThree() 初始化对象。
int book(int startTime, int endTime) 返回一个整数 k，表示日历中存在的最大 k 次预订数。

示例

text

输入：
["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]

解释

text

MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // return 1
myCalendarThree.book(50, 60); // return 1
myCalendarThree.book(10, 40); // return 2
myCalendarThree.book(5, 15);  // return 3
myCalendarThree.book(5, 10);  // return 3
myCalendarThree.book(25, 55); // return 3

约束

0 <= startTime < endTime <= 10^9
调用 book 的次数最多为 400

核心思路

前两题是在判断：

729：能不能插入
731：会不会出现三重预订

而这题变成：

每次插入后，问你当前最多有几个区间同时重叠。

这就不是“拒绝插入”的问题了，而是“统计最大重叠数”的问题。

所以这题最核心的观察是：

一个区间 [start, end) 可以看成：
- 在 start 位置让活跃区间数 +1
- 在 end 位置让活跃区间数 -1
把所有时间点按顺序扫一遍
扫描过程中的前缀和最大值，就是答案

这题至少有两种常见做法：

解法一：差分 + 每次排序扫描
解法二：动态开点线段树

对于 LeetCode 这题的 400 次调用，其实第一种方法已经完全够用；第二种方法更适合理解“如何处理超大区间范围”。

解法一：差分 + 每次排序扫描

这是最推荐先掌握的做法。

思路拆解

我们用一个 Map<number, number> 记录每个时间点的增量：

start 记 +1
end 记 -1

每次 book(start, end) 时：

更新差分表
取出所有时间点并排序
从小到大扫描前缀和
维护扫描过程中的最大值
返回这个最大值

为什么这样做是对的？

假设现在有这些区间：

text

[10, 20), [10, 40), [5, 15)

对应差分变化：

5 -> +1
10 -> +2
15 -> -1
20 -> -1
40 -> -1

从左到右扫描：

到 5：活跃数 = 1
到 10：活跃数 = 3
到 15：活跃数 = 2
到 20：活跃数 = 1
到 40：活跃数 = 0

其中最大值 3，就是当前最大重叠数。

一步一步写出算法

第一步：定义差分表

class MyCalendarThree {
    private diff: Map<number, number>

    constructor() {
        this.diff = new Map()
    }
}

第二步：加入新区间的影响

this.diff.set(startTime, (this.diff.get(startTime) ?? 0) + 1)
this.diff.set(endTime, (this.diff.get(endTime) ?? 0) - 1)

第三步：把所有时间点排序

const times = Array.from(this.diff.keys()).sort((a, b) => a - b)

第四步：扫描前缀和并维护最大值

let active = 0
let answer = 0

for (const time of times) {
    active += this.diff.get(time)!
    answer = Math.max(answer, active)
}

第五步：返回答案

return answer

代码实现（TypeScript）

class MyCalendarThree {
    private diff: Map<number, number>

    constructor() {
        this.diff = new Map()
    }

    book(startTime: number, endTime: number): number {
        this.diff.set(startTime, (this.diff.get(startTime) ?? 0) + 1)
        this.diff.set(endTime, (this.diff.get(endTime) ?? 0) - 1)

        const times = Array.from(this.diff.keys()).sort((a, b) => a - b)
        let active = 0
        let answer = 0

        for (const time of times) {
            active += this.diff.get(time)!
            answer = Math.max(answer, active)
        }

        return answer
    }
}

复杂度分析

假设当前有 m 个不同时间点
排序复杂度：O(m log m)
扫描复杂度：O(m)
单次 book 时间复杂度：O(m log m)
空间复杂度：O(m)

因为本题最多只有 400 次调用，所以 m 最多也就接近 800，完全可以接受。

这一解法的优缺点

优点：

最容易理解
最贴合题目本质
代码非常短

缺点：

每次都要重新排序并扫描
如果调用次数非常多，会显得不够高效

解法二：动态开点线段树

这个做法更偏进阶，适合你想进一步理解：

当区间范围很大（到 10^9）时，如何高效做区间加法和区间最大值查询。

思路拆解

我们把整个时间轴看成一个大区间：

text

[0, 10^9]

每来一个新区间 [startTime, endTime)，就等价于：

在区间 [startTime, endTime - 1] 上全部 +1
然后查询整个区间的最大值

所以这题其实是一个标准问题：

区间加一
查询全局最大值

由于范围太大，不可能真的开一个长度为 10^9 的数组。

因此我们使用：

动态开点：只在访问到的节点上创建对象
懒标记：区间整体加一时，不立刻下推到所有子节点

线段树里每个节点维护什么？

每个节点维护两个值：

max：当前区间内的最大重叠数
lazy：当前区间整体需要补加的懒标记

当一个区间被完整覆盖时：

node.max += 1
node.lazy += 1

当只部分覆盖时：

递归更新左右孩子
再用左右孩子的 max 更新当前节点的 max

一步一步写出算法

第一步：定义节点结构

class SegmentTreeNode {
    left: SegmentTreeNode | null = null
    right: SegmentTreeNode | null = null
    max = 0
    lazy = 0
}

第二步：写区间更新函数

更新目标是给 [start, end] 整段加一。

如果当前节点区间被完全覆盖，直接更新 max 和 lazy
否则递归更新左右子树
最后回溯更新当前节点的 max

第三步：每次 `book` 调用更新区间

因为题目是半开区间 [startTime, endTime)，所以在线段树里要更新成：

[startTime, endTime - 1]

第四步：返回根节点最大值

根节点维护的就是整个时间轴上的最大重叠数。

代码实现（TypeScript）

class SegmentTreeNode {
    left: SegmentTreeNode | null = null
    right: SegmentTreeNode | null = null
    max = 0
    lazy = 0
}

class MyCalendarThree {
    private root: SegmentTreeNode
    private readonly leftBound = 0
    private readonly rightBound = 1_000_000_000

    constructor() {
        this.root = new SegmentTreeNode()
    }

    private update(
        node: SegmentTreeNode,
        left: number,
        right: number,
        start: number,
        end: number,
    ): void {
        if (start <= left && right <= end) {
            node.max += 1
            node.lazy += 1
            return
        }

        const mid = Math.floor((left + right) / 2)

        if (start <= mid) {
            if (node.left === null) {
                node.left = new SegmentTreeNode()
            }
            this.update(node.left, left, mid, start, end)
        }

        if (end > mid) {
            if (node.right === null) {
                node.right = new SegmentTreeNode()
            }
            this.update(node.right, mid + 1, right, start, end)
        }

        const leftMax = node.left?.max ?? 0
        const rightMax = node.right?.max ?? 0
        node.max = node.lazy + Math.max(leftMax, rightMax)
    }

    book(startTime: number, endTime: number): number {
        this.update(this.root, this.leftBound, this.rightBound, startTime, endTime - 1)
        return this.root.max
    }
}

复杂度分析

假设时间轴范围是 U = 10^9
单次区间更新复杂度：O(log U)
单次 book 时间复杂度：O(log U)
空间复杂度：和实际访问到的节点数有关，通常写作 O(n log U)

这个做法的重点不是本题必须用，而是它展示了：

当值域巨大时，可以用动态开点线段树来避免开超大数组。

两种解法对比

解法	核心思想	单次时间复杂度	空间复杂度	特点
差分 + 排序扫描	统计每个时间点的增减变化	`O(m log m)`	`O(m)`	最简单，最推荐先掌握
动态开点线段树	区间加一 + 查询全局最大值	`O(log U)`	`O(n log U)`	更进阶，适合大值域问题

如果你只是为了 LeetCode 通过并且顺便理解题意，第一种方法已经足够。

如果你在准备算法面试，第二种方法值得理解，因为它是一个很经典的模板。

手动模拟一遍差分法

我们还是用题目示例：

text

book(10, 20) -> 1
book(50, 60) -> 1
book(10, 40) -> 2
book(5, 15)  -> 3

第一次：`book(10, 20)`

差分表：

text

10: +1
20: -1

扫描最大值是 1。

第二次：`book(50, 60)`

差分表变成：

text

10: +1
20: -1
50: +1
60: -1

最大同时重叠数仍然是 1。

第三次：`book(10, 40)`

差分表变成：

text

10: +2
20: -1
40: -1
50: +1
60: -1

扫描时：

到 10，活跃数变成 2
到 20，活跃数降到 1

所以答案变成 2。

第四次：`book(5, 15)`

差分表再更新：

text

5:  +1
10: +2
15: -1
20: -1
40: -1
50: +1
60: -1

扫描时：

到 5，活跃数 = 1
到 10，活跃数 = 3

所以答案变成 3。

面试时最容易错的点

1. 半开区间别忘了

题目是 [startTime, endTime)。

这意味着：

在差分法里，startTime 做 +1，endTime 做 -1
在线段树里，要更新的是 [startTime, endTime - 1]

这一点特别容易写错。

2. 这题不需要拒绝预订

729 和 731 都是在判断“能不能订”。

但 732 不一样：

每次预订都一定成功
问题只是成功之后，当前最大重叠数是多少

所以不要写成“冲突了就返回 false”那种逻辑。

3. 差分法的答案是“扫描过程中的最大值”

不是最后的前缀和值。

我们要的是：

answer = Math.max(answer, active)

而不是只看扫描结束时的 active。

一句话总结

这题的本质是：

每次加入一个新区间后，求当前所有时间点上的最大覆盖次数。

最直观的做法就是：

start 记 +1
end 记 -1
排序后扫描前缀和
最大前缀和就是答案

732. 我的日程安排表 III

题目描述

示例

解释

约束

核心思路

解法一：差分 + 每次排序扫描

思路拆解

为什么这样做是对的？

一步一步写出算法

第一步：定义差分表

第二步：加入新区间的影响

第三步：把所有时间点排序

第四步：扫描前缀和并维护最大值

第五步：返回答案

代码实现（TypeScript）

复杂度分析

这一解法的优缺点

解法二：动态开点线段树

思路拆解

线段树里每个节点维护什么？

一步一步写出算法

第一步：定义节点结构

第二步：写区间更新函数

第三步：每次 book 调用更新区间

第四步：返回根节点最大值

代码实现（TypeScript）

复杂度分析

两种解法对比

手动模拟一遍差分法

第一次：book(10, 20)

第二次：book(50, 60)

第三次：book(10, 40)

第四次：book(5, 15)

面试时最容易错的点

1. 半开区间别忘了

2. 这题不需要拒绝预订

3. 差分法的答案是“扫描过程中的最大值”

一句话总结

推荐你最后记住的标准写法

第三步：每次 `book` 调用更新区间

第一次：`book(10, 20)`

第二次：`book(50, 60)`

第三次：`book(10, 40)`

第四次：`book(5, 15)`