LeetCode 732. 我的日程安排表 III
题目描述
题意分析
每次接受一个新的半开预订区间
[start, end)，返回所有已预订日程在同一时刻的最大重叠数量。即使新区间与已有日程重叠，也要保存并参与后续统计。
解法：差分 + 有序映射扫描
核心思路
[!blue]
同时预订数量只会在区间端点发生变化，不需要遍历整条时间轴。用
delta[t]记录时刻t的净变化：一个预订在start开始时加一，在end结束时减一。每次调用只向这两个端点累加变化，其余历史记录保留。把所有端点按时间升序扫描，用
active累加差分。处理完时刻t的变化后，active就是从t到下一个端点之前的活跃预订数，因为此前开始的都已加上，此时及此前结束的都已扣除。相邻端点之间数量不变，所以这些前缀和的最大值就是全局最大重叠数。相同时间的开始和结束必须合并成一个净变化，再更新最大值。这样结束于
t的区间已经退出，开始于t的区间才进入，符合半开区间语义，不会把仅在端点相接的预订额外算作重叠。Java 的
TreeMap按时间顺序遍历值；Go 的映射无序，必须先收集并排序键。每次从头扫描时，active和本轮答案都重置为 0，但差分表不能清空，否则会丢掉历史日程。题目最多调用 400 次，逐次扫描全部端点足够。
解题步骤
- 将开始端点的差分加一，结束端点的差分减一。
- 按时间顺序遍历全部差分端点。
- 累加活跃数量，并维护本轮最大值。
- 返回最大值，保留差分表供后续插入。
代码实现
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;
}
}
import "sort"
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
}
复杂度分析
- 时间复杂度：本次加入后共有
m个不同端点时，Java 单次为 $O(m)$，Go 单次为 $O(m\log(m+1))$。每次最多增加两个端点，连续q次调用最坏累计分别为 $O(q^2)$ 和 $O(q^2\log(q+1))$。- 空间复杂度：$O(m)$，保存端点差分，Go 另保存排序键。
关键点总结
[!green]
- 差分记录变化量，前缀和才是同时预订数量。
- 同时间的增减应合并，保持半开区间语义。
- 求的是同一时刻的最大覆盖数，不是累计预订总数。
易错点总结
[!yellow]
- 直接取最大差分值：忽略此前仍未结束的预订。
- 无序遍历端点求前缀和：时间顺序不成立。
- 结束端点也加一：活跃数量只增不减。
- 把 Go 每次排序省略在复杂度之外：低估单次操作成本。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 731. 我的日程安排表 II | 中等 | 原题超过双重预订就拒绝，本题始终接受并返回当前最大重叠数。 |
| 253. 会议室 II | 中等 | 同样统计时间区间最大并发，原题全部会议预先给出，本题要支持逐次增加。 |
| 729. 我的日程安排表 I | 中等 | 日程安排表系列。I 拒绝重叠预订；III 接受全部预订，并用端点差分统计最大重叠数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！