我的日程安排表如何判断预定冲突？（LeetCode 729）

简化版

设计一个日程表，支持 book(start, end)：预定一个左闭右开区间 [start, end)，若它和已有预定不重叠就成功（返回 true 并记录），否则失败（返回 false）。核心是动态地维护一堆不重叠区间并快速判重叠。最优做法用有序集合（如 Java 的 TreeMap，按 start 排序）：插入前用 floorKey/ceilingKey 找到相邻的前一个和后一个区间，只需检查这两个是否与新区间冲突，O(log n) 完成。

详细版

class MyCalendar {
    private TreeMap<Integer, Integer> calendar = new TreeMap<>();  // start -> end

    public boolean book(int start, int end) {
        Integer prev = calendar.floorKey(start);     // 起点 <= start 的最近区间
        Integer next = calendar.ceilingKey(start);   // 起点 >= start 的最近区间
        // 与前一个冲突：前区间的 end > 新的 start
        if (prev != null && calendar.get(prev) > start) return false;
        // 与后一个冲突：新的 end > 后区间的 start
        if (next != null && end > next) return false;
        calendar.put(start, end);                    // 无冲突，记录
        return true;
    }
}

左闭右开 [start, end)：[1,3) 和 [3,5) 不冲突（3 这个点不属于前者）。
只需查相邻两个：因为已存区间互不重叠，新区间只可能和「按 start 排序后紧邻的前后两个」冲突。
TreeMap 的 floorKey/ceilingKey：O(log n) 找前驱后继。
复杂度：每次 book O(log n)，n 次预定共 O(n log n)。

完整版教学

一、题目本质：动态维护不重叠区间集合

和「合并区间」这种一次性处理静态区间不同，本题是在线的：区间一个个到来，每来一个要立刻判断能否加入（不与已有的重叠），能则加入。所以需要一个能动态插入、又能高效查重叠的数据结构。

最朴素的做法是用列表存所有已预定区间，每次 book 遍历全部判重叠——O(n) 每次、总 O(n²)。优化目标是把「判重叠」降到 O(log n)。

二、关键洞察：只可能和相邻区间冲突

因为已存的区间两两不重叠，把它们按 start 排序后是一排互不相交的段。新区间 [start, end) 要插进去，它只可能和按 start 排序后紧挨着它的前一个、后一个区间发生冲突——不可能跳过相邻的去和更远的区间重叠（中间隔着的相邻区间会先挡住）。所以只需检查两个邻居，这是把复杂度降下来的钥匙。

三、用 TreeMap 找前驱后继

Java 的 TreeMap（红黑树）按 key 有序，提供 O(log n) 的：

floorKey(start)：返回 ≤ start 的最大 key（前一个区间的起点 prev）。
ceilingKey(start)：返回 ≥ start 的最小 key（后一个区间的起点 next）。

冲突判断（左闭右开 [start, end) 语义）：

和前一个冲突：前区间 [prev, calendar.get(prev)) 的结束 > 新的 start，即 calendar.get(prev) > start。（若等于 start，前区间在 start 处已结束，不冲突。）
和后一个冲突：新区间的结束 > 后区间的起点，即 end > next。（若等于，新区间在 next 处结束，不冲突。）

两个都不冲突才 put 记录。

四、左闭右开的边界处理

题目区间是 [start, end) 左闭右开，这决定了所有比较用严格 >：

[1,3) 和 [3,5)：前者结束点 3 不包含，后者从 3 开始，不冲突。对应 calendar.get(prev)=3 > start=3 为 false，正确判为不冲突。
若是闭区间 [start, end]，相接就算冲突，要改用 >=。

左闭右开 → 用 >；闭区间 → 用 >=。这是本题最常见的边界坑。

五、其他解法与进阶

暴力列表 O(n²)：每次遍历所有区间判 Math.max(s1,s2) < Math.min(e1,e2)。简单但慢，小数据可用。
进阶 My Calendar II（731）：允许两次重叠、第三次才拒绝，需要维护「重叠区间」的额外结构或用差分/线段树。
进阶 My Calendar III（732）：求最大重叠次数，用线段树 / 差分（TreeMap 计数扫描）。

本题（I）用 TreeMap 找相邻是最优雅的标准解，务必掌握。

六、排序键、扫描不变量与边界语义

本题扫描成立的结构是：动态集合按 start 排序；新 [s,e) 只需检查前驱 end≤s 与后继 start≥e。

更远区间被相邻区间挡住：若前驱不冲突，更早区间结束只会更早；后继同理

数字推演：已有 [10,20)、[30,40)，[20,30) 可插入，而 [15,25) 与前驱冲突。

扫描过程中要始终说明已经处理部分被压缩成什么状态，以及为什么更早区间不必再看。实现边界是：TreeMap 不能用相同 start 覆盖旧预订；日程采用半开区间；并发调用需要同步。

记忆钩子：区间题先写端点语义，再选排序键；小于还是小于等于不是代码风格，而是问题定义。

七、方法对比与专项测试

问题结构	常用工具
静态合并或覆盖	排序后线性扫描
选择最多不重叠	按右端排序的贪心
最大同时重叠	扫描线或最小堆
两个有序列表求交	双指针
动态预约	有序树或线段树

测试必须覆盖空输入、单区间、完全分离、完全嵌套、链式重叠、相同起点或终点，以及端点恰好相接。若排序比较器用端点相减，还要加入整数极值检查溢出。

正确性复核要落到本题的排除逻辑：动态集合按 start 排序；新 [s,e) 只需检查前驱 end≤s 与后继 start≥e。这保证扫描指针越过某段后，它不可能再与未来候选形成更优或遗漏的答案。

已处理区间 ──压缩为边界/堆/结果尾段──> 当前区间
       │                                  │
       └─ 已由排序与端点关系证明无需回看 ─┘
当前决策完成后，指针只向右移动

在数字样例“已有 [10,20)、[30,40)，[20,30) 可插入，而 [15,25) 与前驱冲突”上，应逐轮写出被保留的边界和被丢弃的区间。若某一步无法解释为什么丢弃安全，就说明排序键、端点不等号或状态定义仍有问题。

工程上还要单独确认：TreeMap 不能用相同 start 覆盖旧预订；日程采用半开区间；并发调用需要同步。这些条件变化会直接改变重叠判定或所需数据结构，不能只修改一个比较符后沿用原证明。

八、常见误区与追问

误区：新预约要与所有旧预约比较。 有序集合中只需检查前驱后继。
误区：闭区间判断更安全。 日程通常是 [start,end)，相接不冲突。
误区：TreeMap put 会自动拒绝冲突。 它只按 key 存储，冲突逻辑必须自己判断。
追问：为何只查相邻？ 有序性使更远区间被最近前驱/后继支配。
追问：相同 start 怎么办？ 必与旧区间冲突，不能覆盖其 value。
追问：更高阶版本如何做？ 允许双重预订可用扫描线动态计数或线段树。

九、加强记忆

我的日程安排表 I = 动态维护不重叠区间 + 只查相邻两个判冲突。关键洞察：已存区间互不重叠，新区间只可能和按 start 排序的前驱、后继冲突。用 TreeMap（start→end）的 floorKey/ceilingKey O(log n) 找前后邻居：和前一个冲突当 prev.end > start，和后一个冲突当 end > next.start，都不冲突才 put。左闭右开 [start,end) 用严格 >（相接不冲突），闭区间才用 >=。每次 O(log n)。进阶 II/III 用差分或线段树。

简化版

详细版