LeetCode 732. 我的日程安排表 III

2023-11-20 HGNULB 约 13 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 732. 我的日程安排表 III

题意分析

设计一个日程表类，book(start, end) 每次加入一个半开区间 [start, end)。与 I、II 两问不同的是，这里所有预定都无条件接受，永远不会被拒绝；每次调用要返回当前全部预定所形成的最大重叠层数 $k$，也就是存在某个时刻同时被 $k$ 个区间覆盖，且 $k$ 是所有时刻中的最大值。

「无条件接受」这句话大幅改变了问题性质。既然不需要判定冲突，就不再关心「哪两个区间相交」，只关心「时间轴上每个点被覆盖了几次」。问题从区间之间的两两关系，塌缩成了一条数轴上的计数函数求最大值。这个视角切换是解本题的第一步。

半开区间的语义在这里同样关键：区间在 end 这一刻已经结束，所以 [10, 20) 与 [20, 30) 的重叠层数是 1 而不是 2。任何计数方案都必须让 end 处的减一与 start 处的加一在同一个时刻正确抵消。

约束给的信号很直白：调用次数最多 400 次，$0 \le start < end \le 10^9$。值域大到不可能开数组，但调用次数小到离谱——400 次调用意味着时间轴上最多只有 800 个「有意义的时刻」，而 $400 \times 800$ 不过三十来万次操作。这明确告诉你：不需要线段树，每次调用重扫一遍全部事件点完全来得及。约束里的 400 就是出题人给的许可证，看到它就该放弃复杂结构。

边界方面：第一次调用时表里只有这一个区间，答案必然是 1；完全不相交的多个区间，答案始终是 1；同一个区间被重复预定 $m$ 次，答案就是 $m$。这些都应该由统一的计数逻辑自然得出，而不需要特判。

解法：差分 + 有序映射扫描

核心思路

暴力的想法是：每次预定后，枚举任意一对区间求交集，统计最大的公共覆盖数。但「最大重叠层数」并不是两两相交能直接得出的——三个区间两两相交却没有公共点的情形是存在的（例如 [0,3)、[2,5)、[4,7) 两两相交但最大层数只有 2）。所以两两比较这条路本身就不成立，必须转向逐点覆盖计数。

逐点计数的朴素形式是给时间轴上每个整数点开一个计数器，区间 [start, end) 就把 start 到 end-1 的计数器全部加一，最后取最大值。这在语义上完全正确，瓶颈只有一个：值域是 $10^9$，开不出这么大的数组，而且单次区间加一是 $O(len)$ 的。

突破口是差分。既然我们只需要覆盖函数的最大值，就不必存函数本身，只需存它的变化量。定义 $delta[t]$ 表示「在时刻 $t$ 覆盖层数相对于 $t$ 之前发生的净变化」。一个区间 [start, end) 对应两次修改：$delta[start]$ 加一（从这一刻起多了一层），$delta[end]$ 减一（到这一刻这层没了）。差分把「区间上的整段修改」压缩成了两个端点上的常数修改，这是本题效率的全部来源。

有了 $delta$，覆盖函数就是它的前缀和：把所有出现过的时刻按时间升序排列，用一个累加器 $active$ 从 0 开始依次加上每个时刻的 $delta$ 值，$active$ 在某个时刻之后的取值就是该时刻的覆盖层数。答案是扫描过程中 $active$ 取到的最大值。这里的不变量是：扫描到时刻 $t$ 并累加完 $delta[t]$ 之后，$active$ 恰好等于区间 $[t, t')$ 上的覆盖层数（$t'$ 是下一个事件时刻）。因为两个相邻事件点之间覆盖层数是常数，只在事件点处跳变，所以只检查事件点就足以找到全局最大值，中间的连续区间可以完全跳过——这正是「离散化」的本质。

半开区间的正确性由此自然成立：[10,20) 与 [20,30) 在时刻 20 处，$delta[20]$ 同时收到 -1（前者结束）和 +1（后者开始），净变化为 0，$active$ 从 1 变成 1，不会出现虚假的 2。关键在于同一时刻的所有增减必须合并到同一个键上再一次性累加，若把加和减分成两条记录且减排在加之后，就会瞬时出现 2。用映射以时刻为键做累加，天然满足这个要求。

容器的选择：Java 的有序映射按键升序迭代，所以每次调用只需两次更新加一次线性遍历。Go 没有有序映射，用普通哈希表存 $delta$，每次调用把键取出来排序再扫。键的数量最多是调用次数的两倍，在 400 次调用的约束下，每次排序 800 个元素、共 400 次，代价完全可以接受。

解题步骤

第一步，准备一个「时刻 → 净变化量」的映射作为类的成员状态。 为什么状态要跨调用保留：这是设计类题目，book 返回的是截至目前所有预定的最大重叠数，历史预定必须持续存在于结构中。

第二步，本次预定令 $delta[start]$ 加一。 为什么是加在 start 上：区间从 start 这一刻开始生效，start 本身被覆盖。

第三步，令 $delta[end]$ 减一。 为什么是 end 而不是 end - 1：半开区间不包含 end，所以覆盖恰好在 end 这一刻消失。若写成 end - 1，区间的最后一个单位时间就被少算了一层。

第四步，取出全部时刻并按升序排列。 为什么必须有序：差分数组的前缀和只有沿时间正方向累加才有意义，顺序一乱，$active$ 在中途会取到没有物理含义的值（甚至为负），最大值随之失真。Java 的有序映射天然满足，Go 需要显式排序。

第五步，令 $active = 0$、$answer = 0$，按序遍历每个时刻，先把该时刻的净变化量累加进 $active$，再用 $active$ 更新 $answer$。 为什么是先累加后取最大：$active$ 在累加之前代表的是上一段区间的层数，已经在上一轮被统计过了；累加之后才代表当前时刻起的层数。顺序反了会漏掉最后一次抬升。

第六步，返回 $answer$。 为什么不需要维护一个跨调用的历史最大值：最大重叠层数只会随着预定增加而单调不减，每次重新扫描得到的就是当前的全局最大，不存在需要「记住旧答案」的情形；但反过来说，也不能只检查本次新增区间附近的层数，因为新区间可能把某个原本层数就高的地方顶得更高，也可能不影响峰值。

以调用序列 book(10,20)、book(50,60)、book(10,40)、book(5,15)、book(5,10)、book(25,55) 走一遍。

book(10, 20)：$delta$ 更新为 ${10: +1,\ 20: -1}$。按序扫描：时刻 10，$active = 1$，$answer = 1$；时刻 20，$active = 0$。返回 1。

book(50, 60)：$delta = {10: +1,\ 20: -1,\ 50: +1,\ 60: -1}$。扫描：10 → $active = 1$（$answer = 1$）；20 → 0；50 → 1；60 → 0。返回 1。两个区间不相交，峰值仍是 1，这一步验证了「不相交时 $active$ 会回落到 0 再抬起」。

book(10, 40)：时刻 10 上已有 +1，累加后变成 +2；时刻 40 记 -1。$delta = {10: +2,\ 20: -1,\ 40: -1,\ 50: +1,\ 60: -1}$。扫描：10 → $active = 2$，$answer = 2$；20 → 1；40 → 0；50 → 1；60 → 0。返回 2。注意时刻 10 的两次加一被合并成一个键上的 +2，一次累加就跳到 2，这正是「同一时刻的变化必须合并」的作用。

book(5, 15)：$delta = {5: +1,\ 10: +2,\ 15: -1,\ 20: -1,\ 40: -1,\ 50: +1,\ 60: -1}$。扫描：5 → 1；10 → 3，$answer = 3$；15 → 2；20 → 1；40 → 0；50 → 1；60 → 0。返回 3。区间 [10,15) 被三个预定同时覆盖。

book(5, 10)：时刻 5 变成 +2，时刻 10 收到 -1 后从 +2 变成 +1。$delta = {5: +2,\ 10: +1,\ 15: -1,\ 20: -1,\ 40: -1,\ 50: +1,\ 60: -1}$。扫描：5 → 2；10 → 3，$answer = 3$；15 → 2；20 → 1；40 → 0；50 → 1；60 → 0。返回 3。这一步最能说明半开区间的处理：[5,10) 在时刻 10 结束、[10,20) 和 [10,40) 在时刻 10 开始，三者在同一个键上净变化为 $-1+2 = +1$，$active$ 从 2 平滑升到 3，而不是先虚假地冲到 4 再掉下来。如果把加和减拆成两个先后处理的事件且减在后，就会读出错误的 4。

book(25, 55)：$delta = {5: +2,\ 10: +1,\ 15: -1,\ 20: -1,\ 25: +1,\ 40: -1,\ 50: +1,\ 55: -1,\ 60: -1}$。扫描：5 → 2；10 → 3（$answer = 3$）；15 → 2；20 → 1；25 → 2；40 → 1；50 → 2；55 → 1；60 → 0。返回 3。新区间虽然与多个已有区间相交，但没能把任何位置顶到 3 以上，答案维持不变——这说明为什么不能只看新区间就下结论，也说明为什么每次都要完整重扫。

代码实现

class MyCalendarThree {
    private final TreeMap<Integer, Integer> delta = new TreeMap<>();

    public int book(int start, int end) {
        delta.put(start, delta.getOrDefault(start, 0) + 1);
        delta.put(end, delta.getOrDefault(end, 0) - 1);

        int active = 0;
        int answer = 0;
        for (int v : delta.values()) {
            active += v;
            answer = Math.max(answer, active);
        }
        return answer;
    }
}

type MyCalendarThree struct {
    delta map[int]int
}

func Constructor() MyCalendarThree {
    return MyCalendarThree{delta: make(map[int]int)}
}

func (c *MyCalendarThree) Book(start int, end int) int {
    c.delta[start]++
    c.delta[end]--

    keys := make([]int, 0, len(c.delta))
    for t := range c.delta {
        keys = append(keys, t)
    }
    sort.Ints(keys)

    active := 0
    answer := 0
    for _, t := range keys {
        active += c.delta[t]
        if active > answer {
            answer = active
        }
    }
    return answer
}

复杂度分析

时间复杂度：Java 版单次 book 是 $O(n)$——两次有序映射更新各 $O(\log n)$，随后按序遍历全部事件点 $O(n)$，其中 $n$ 是已有事件点数量（不超过调用次数的两倍）。$m$ 次调用总计 $O(m^2)$。Go 版单次是 $O(n \log n)$，多出的是每次把键收集起来重新排序的开销，总计 $O(m^2 \log m)$。在 $m \le 400$ 的约束下，Java 约 $3 \times 10^5$ 次操作，Go 约 $3 \times 10^6$ 次，都远在限制之内。

空间复杂度：$O(m)$，$m$ 为调用次数。每次预定最多新增两个事件点，映射的规模因此与调用次数同阶；Go 版额外用一个等长的键切片，不改变数量级。注意这里的空间与值域 $10^9$ 完全无关——只存出现过的时刻，是差分配合离散化的直接收益。

关键点总结

求「最大重叠层数」要转成逐点覆盖计数，而不是两两求交。三个区间可以两两相交却无公共点，所以任何基于「有多少对区间相交」的推理都会给出错误答案。把区间问题投影到数轴上的计数函数，是这类题的统一入口。

差分把区间修改压成端点修改。只关心覆盖函数的极值时，没必要存函数本身，存它的一阶差分即可：区间加一变成首端加一、尾端减一，$O(len)$ 变 $O(1)$。这个变换可以原样迁移到航班预订、拼车、区间加法等一整类题。

值域大而事件少时，用映射代替数组完成隐式离散化。相邻事件点之间覆盖层数恒定，所以只需在事件点采样。以时刻为键的有序结构同时解决了「不开大数组」和「按时间有序扫描」两个需求。

同一时刻的增减必须合并到同一个键上。这是半开区间语义正确的技术前提。用映射累加而不是往列表里追加事件对，天然规避了「同刻先减后加」还是「先加后减」的排序歧义。

先累加再取最大值，顺序不可交换。差分前缀和的语义是「累加完当前时刻的变化后，$active$ 才代表从此刻起的层数」。这条在所有扫描线题目里都一样。

面试视角：面试官关心的是你能否说清三件事——为什么两两求交不行、差分为什么正确、半开区间在同一时刻的抵消如何保证。讲的时候要主动写出「$active$ 在累加完 $delta[t]$ 后等于 $[t, t')$ 上的覆盖层数」这个不变量，它是整段代码的证明。如果被追问「调用次数放大到 $10^5$ 怎么办」，正确回答是换成动态开点线段树或离散化后的线段树，用区间加、区间求最大值把单次调用降到 $O(\log C)$；同时要点明本题给的 400 次上限就是在暗示不需要上线段树，能识别约束的暗示本身就是加分项。

易错点总结

错误写法：区间结束记在 end - 1 上，即 $delta[end-1]$ 减一。以 book(10,20) 后 book(19,25) 为例，正确答案是 2（时刻 19 被两个区间覆盖），但错误写法在时刻 19 处会把第一个区间提前结束，$active$ 只到 1，返回 1。半开区间的减一必须落在 end 上。

错误写法：把事件存成 (时刻, +1) 和 (时刻, -1) 的列表，排序时同刻的减排在加之后。以 book(5,10) 后 book(10,20) 为例，时刻 10 处先处理 +1 再处理 -1，$active$ 会瞬时冲到 2，返回 2，而正确答案是 1。用映射按键累加可以从根本上消灭这个陷阱。

错误写法：不排序，直接遍历哈希表的键。以 book(10,20) 后 book(50,60) 为例，若遍历顺序是 20、50、10、60，$active$ 依次变成 -1、0、1、0，$answer$ 得 1 只是碰巧；换成 book(5,15)、book(10,20) 这类嵌套输入，无序遍历给出的最大值会小于真实值。Go 的 map 遍历顺序是随机化的，漏掉排序会导致同一份输入多次运行结果不同。

错误写法：先用 $active$ 更新 $answer$ 再累加当前时刻的变化量。以单次 book(10,20) 为例，时刻 10 处先记录 $answer = 0$ 再让 $active$ 变 1，时刻 20 处先记录 $answer = 1$ 再让 $active$ 归零，最终返回 1 侥幸正确；但换成 book(10,20)、book(10,20) 两次相同预定，时刻 10 的净变化是 +2，先记录 $answer$ 会漏掉这次抬升，返回 1 而正确答案是 2。

错误写法：只在新区间覆盖的范围内扫描求最大值。以先 book(10,20) 三次（此时答案为 3）再 book(100,200) 为例，只扫 [100,200) 会得到 1，返回 1 而正确答案仍是 3。最大重叠层数是全局量，每次都必须扫全部事件点。

错误写法：用一个跨调用的成员变量缓存历史最大值，本次只比较新区间附近。以 book(10,20)、book(15,25)、book(12,18) 为例，第三次调用把 [15,18) 顶到了 3，若只比较新区间两端点 12 和 18 处的层数（分别是 2 和 1，因为 18 处 [12,18) 已结束），会漏掉区间内部的峰值，返回 2 而正确答案是 3。峰值可能出现在新区间内部的任意事件点上。

错误写法：Java 里用普通 HashMap 而不是有序映射，直接 for (int v : map.values())。以 book(10,20)、book(50,60) 为例，HashMap 的迭代顺序由哈希值决定，与时间无关，$active$ 的中间值毫无意义，返回结果随实现细节漂移。这个错误在小数据上常常侥幸通过，极难调试。

错误写法：把 $delta$ 换成「起点集合」和「终点集合」两个独立的有序结构分别扫描。以 book(5,10)、book(10,20) 为例，两个集合无法表达「同刻净变化」，无论先扫哪个都会给出 2 或 0 的瞬时错值。增减必须在同一条时间轴上合并。

错误写法：以为可以在插入时增量更新答案，只把 $active$ 在新增两点处加减。以 book(0,100)、book(0,100)、book(50,60) 为例，第三次的增量思路会认为新增区间只让层数加一得到 2，但 [50,60) 实际已被三层覆盖，正确答案是 3。差分数组的前缀和不支持这种局部增量推导，必须重扫。

错误写法：$answer$ 初值设为 1。虽然本题至少有一次预定使答案不小于 1，看似无害；但一旦把类复用到「构造后先查询」的场景，未预定时会错误返回 1。让 $answer$ 从 0 起并由扫描自然抬升，语义才自洽。

错误写法：Go 里忘记 c.delta[end]-- 中 end 键可能与已有 start 键重合而覆盖赋值，写成 c.delta[end] = -1。以 book(10,20) 后 book(20,30) 为例，第二次预定的 c.delta[20] = 1 会覆盖掉第一次留下的 -1，时刻 20 的净变化变成 +1 而非 0，$active$ 一路涨到 2，返回 2 而正确答案是 1。必须用累加而非赋值。

相似题目

题目	难度	考察点
729. 我的日程安排表 I	中等	只允许零重叠，重点是插入前查前驱后继做冲突判定，无需计数
253. 会议室 II	中等	离线给全部区间求同一峰值，可用最小堆维护进行中的会议，答案含义相同解法不同
1094. 拼车	中等	差分权重不再是 1 而是乘客数，且只需判断峰值是否超载而非返回峰值
1109. 航班预订统计	中等	差分后要还原整条前缀和数组而非只取最大值，且值域小可直接开数组
218. 天际线问题	困难	同为扫描线，但要输出每个高度变化点，需用多重集维护当前最大高度
370. 区间加法	中等	差分的最基础形态，离线批量区间加后一次性求前缀和
252. 会议室	简单	只问峰值是否超过 1，排序后比较相邻区间即可
56. 合并区间	中等	关注的是覆盖区域的连通块而非层数，排序后线性合并