LeetCode 729. 我的日程安排表 I

2022-09-14 HGNULB 约 13 分钟

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

分类

题目描述

✅ 729. 我的日程安排表 I

题意分析

设计一个日程表类，book(start, end) 尝试预定半开区间 [start, end)。如果这次预定与任何一个已经成功预定的区间存在重叠，就拒绝并返回 false，且这次预定不留下任何痕迹；否则接受、记录下来并返回 true。

「半开」是本题最先要吃透的设定。区间包含 start 但不包含 end，所以 [10, 20) 与 [20, 30) 是允许共存的——前者在 20 这一刻已经结束。判定两个半开区间 [a, b) 与 [c, d) 重叠的充要条件是 $\max(a, c) < \min(b, d)$，注意是严格小于。如果误用了小于等于，端点相接的合法预定就会被拒绝。

「失败不留痕」是第二个关键点。必须先完成全部冲突检查、确认无冲突之后才写入，绝不能先插入再回滚。一旦采用「先插后删」的写法，中途返回的分支很容易漏掉删除，状态就被污染了。

约束透露的信号很明确：调用次数最多 1000 次，0 ≤ start < end ≤ 10^9。调用次数只有千级，说明每次预定线性扫一遍已有区间的 $O(n)$ 做法（总计 $10^6$）也能通过，题目并不强制更优解；但值域高达 $10^9$ 且没有说是整数刻度密集使用，直接开值域数组是不可行的，必须以区间为单位存储。真正想考的是：你能否让每次查询只看位置上相邻的那一两个区间，而不是全部扫一遍。

边界方面有三处：日程表为空时第一次预定必然成功，此时前驱和后继都不存在，判断逻辑要能容忍「查不到」；新区间落在所有已有区间之前时只有后继；落在最后时只有前驱。理想的实现应该让这三种情况都自然落进同一套判断，而不是各写一个特判分支。

解法：TreeMap / 有序映射维护区间

核心思路

最朴素的做法是把所有已接受的区间放进一个列表，每次 book 都遍历整个列表，逐个用 $\max(a, c) < \min(b, d)$ 判定。这是对的，但每次预定都要看全部历史区间，第 $i$ 次调用做 $i$ 次比较，总代价 $O(n^2)$。瓶颈在于：绝大多数比较毫无意义——一个远在时间轴另一端的区间，根本不可能与当前区间冲突。

顺着这个观察走下去：如果已有区间按起点有序存放，那么与新区间 [start, end) 可能冲突的候选就被压缩到了极少数几个。更进一步，因为日程表内部始终保持两两互不重叠（这是这个数据结构的核心不变量，由每次插入前的检查保证），所以按起点排序等价于按终点排序，区间在时间轴上是首尾分离、严格递增排列的。

这个不变量带来一个很强的结论：只需要检查起点方向上紧邻的前驱和后继两个区间。设 prev 是起点不超过 start 的那个区间中起点最大的一个，next 是起点不小于 start 的那个区间中起点最小的一个。任何比 prev 更靠前的区间，其终点不超过 prev 的起点，更不可能越过 prev 去和 start 之后的部分相交；同理任何比 next 更靠后的区间，起点不小于 next 的终点，更不可能小于 end。所以两次检查就够了，不需要区间树。

于是冲突条件可以针对这两个候选各写成一条，形式比通用公式更简洁：

与前驱冲突 $\iff$ prev.end > start。因为 prev.start ≤ start 已经成立，两区间的重叠条件 $\max$ 部分必然取 start，$\min$ 部分取 prev.end 或 end；而 prev.end > start 时若 prev.end ≤ end 则重叠区间是 [start, prev.end) 非空，若 prev.end > end 则重叠区间是 [start, end) 非空，两种情况都冲突。

与后继冲突 $\iff$ end > next.start。对称地，start ≤ next.start 成立，重叠的下界取 next.start，上界取 end 与 next.end 的较小者；end > next.start 时重叠区间非空。

剩下的是选容器。Java 有现成的有序映射，floorKey 和 ceilingKey 正好对应上面两个候选，单次查询 $O(\log n)$。Go 标准库没有平衡树，所以用一个按起点升序的切片，自己二分找出「第一个起点不小于 start 的位置 l」——这个 l 就是后继下标，l - 1 就是前驱下标，一次二分同时定位两个候选。插入时把 l 之后的元素整体后移一位，维持有序性。

解题步骤

第一步，定位前驱：起点不超过 start 的最后一个区间。 为什么用「不超过」而不是「严格小于」：如果已有区间的起点恰好等于 start，它必定冲突（两个区间从同一时刻开始，而区间长度都为正），把它归入前驱能让这种情况被前驱检查一并覆盖，不需要单独判等。

第二步，若前驱存在且 prev.end > start，立即返回 false。 为什么只比终点不比起点：前驱的起点已经保证不超过 start，所以是否重叠完全取决于它的终点有没有越过 start。用严格大于是因为半开区间允许 prev.end == start 的首尾相接。

第三步，定位后继：起点不小于 start 的第一个区间。 为什么不是「严格大于 start」：与第一步的划分对应，两次查找共同覆盖全体区间且不遗漏；起点等于 start 的区间既会被前驱检查抓到，也会被后继检查抓到，重复检查无害，遗漏才致命。

第四步，若后继存在且 end > next.start，立即返回 false。 为什么只比起点：后继的起点已经保证不小于 start，是否重叠取决于新区间的终点有没有越过它的起点。

第五步，两项检查都通过后才写入，并返回 true。 为什么必须放在最后：题目要求失败的预定不能改变日程表状态。把插入放在检查之后，所有失败分支都是纯粹的早退，不存在需要回滚的中间状态。

第六步（Go 侧），插入时保持切片按起点升序。 为什么必须维持有序：二分查找的正确性完全依赖这个前提，一旦某次插入直接追加到尾部，后续所有二分结果都会失效，冲突检测彻底失灵。

以调用序列 book(10,20)、book(15,25)、book(20,30)、book(5,15) 走一遍。

book(10, 20)：日程表为空。查前驱，不存在，跳过第一项检查；查后继，不存在，跳过第二项。写入 [10, 20)，返回 true。这一步展示了空表时两个「不存在」的判空为什么必须写在比较之前——先取值再判空会直接空指针或越界。

book(15, 25)：查前驱，起点不超过 15 的最后一个区间是 [10, 20)。检查 prev.end = 20 > 15，成立，返回 false。注意此时并没有执行任何写操作，日程表仍然只有 [10, 20)。

book(20, 30)：查前驱，起点不超过 20 的最后一个区间仍是 [10, 20)。检查 prev.end = 20 > 20，不成立，通过——这正是半开区间允许端点相接的体现，若这里写成 >= 就会误拒。查后继，起点不小于 20 的区间不存在，跳过。写入 [20, 30)，日程表变为 [10,20), [20,30)，返回 true。

book(5, 15)：查前驱，起点不超过 5 的区间不存在，跳过第一项检查。查后继，起点不小于 5 的第一个区间是 [10, 20)。检查 end = 15 > next.start = 10，成立，返回 false。这一步专门检验了后继分支：如果只写了前驱检查而漏掉后继，这次预定会被错误接受，日程表里将同时存在互相重叠的 [5,15) 与 [10,20)，此后所有判定都建立在被污染的状态上。

Go 侧同一序列的下标变化：第一次二分在空切片上得 l = 0，l > 0 与 l < len 都不成立，两项检查自动跳过，插入后切片为 [[10,20)]。第三次调用二分找「第一个起点 ≥ 20 的位置」，切片只有起点 10，得 l = 1；l - 1 = 0 对应 [10,20)，检查 20 > 20 不成立；l = 1 已到末尾，后继不存在。插入到下标 1，切片为 [[10,20),[20,30)]。第四次二分找「第一个起点 ≥ 5 的位置」得 l = 0；l > 0 不成立跳过前驱；l = 0 < 2，检查 15 > 10 成立，返回 false。

代码实现

class MyCalendar {
    private final TreeMap<Integer, Integer> map = new TreeMap<>();

    public boolean book(int start, int end) {
        Integer prevStart = map.floorKey(start);
        if (prevStart != null && map.get(prevStart) > start) {
            return false;
        }

        Integer nextStart = map.ceilingKey(start);
        if (nextStart != null && end > nextStart) {
            return false;
        }

        map.put(start, end);
        return true;
    }
}

type MyCalendar struct {
    intervals [][2]int
}

func Constructor() MyCalendar {
    return MyCalendar{intervals: make([][2]int, 0)}
}

func (c *MyCalendar) Book(start int, end int) bool {
    l, r := 0, len(c.intervals)
    for l < r {
        mid := (l + r) / 2
        if c.intervals[mid][0] < start {
            l = mid + 1
        } else {
            r = mid
        }
    }

    if l > 0 && c.intervals[l-1][1] > start {
        return false
    }
    if l < len(c.intervals) && end > c.intervals[l][0] {
        return false
    }

    c.intervals = append(c.intervals, [2]int{})
    copy(c.intervals[l+1:], c.intervals[l:])
    c.intervals[l] = [2]int{start, end}
    return true
}

复杂度分析

时间复杂度：Java 版每次 book 是 $O(\log n)$，floorKey、ceilingKey、put 都是红黑树上的一次自根向下查找，$n$ 次调用总计 $O(n \log n)$。Go 版查询是 $O(\log n)$ 的二分，但插入需要把 l 之后的元素整体后移，最坏 $O(n)$，单次因此是 $O(n)$，总计 $O(n^2)$；在调用次数上限 1000 的约束下，最坏约 $5 \times 10^5$ 次元素搬移，完全可以接受。

空间复杂度：$O(n)$，$n$ 为成功预定的区间数量。每个接受的区间恰好占一个条目，被拒绝的预定不占空间。除容器本身外只用了常数个下标变量。

关键点总结

先立不变量，再谈查询范围。这道题所有的效率优化都建立在「表内区间两两不重叠且按起点有序」这条不变量上。因为有它，才能从「和所有区间比」收缩到「只和前驱后继比」。遇到设计类题目，第一件事是写下数据结构在任意时刻满足的性质，它决定了你能省掉多少工作。

半开区间用严格不等号，闭区间才用等号。prev.end > start 和 end > next.start 里的严格大于是本题的分水岭。养成习惯：拿到区间题先确认端点开闭，再据此固定所有比较运算符的方向和严格性，之后写代码就不用反复纠结。

前驱后继的划分要覆盖且可重叠，不能有缝。「起点 ≤ start」与「起点 ≥ start」两个查询在等号处重叠了一次，看似冗余，但这保证了任何已有区间至少被一次检查覆盖。设计双向查找时，宁可让两侧多重叠一格，也不要为了「不重复」而在中间留出一个谁都不管的位置。

有副作用的写入必须放在所有校验之后。这是「校验-提交」模式，不只适用于本题，也是并发编程与事务处理的通用纪律。任何「先改再判、失败回滚」的写法都会在多分支返回时留下漏网之鱼。

语言差异要影响容器选择，而不是算法选择。Java 有平衡树就用 TreeMap，Go 没有就用「有序切片 + 手写二分 + 插入搬移」。算法层面完全一致，只是插入的复杂度从 $O(\log n)$ 退化到 $O(n)$，而约束允许这种退化。

面试视角：面试官几乎一定会追问两件事。第一是「为什么只查两个邻居就够」，标准答案是搬出不重叠不变量做归纳论证，而不是说「感觉不会冲突」。第二是「区间数量到 $10^5$、还要支持删除怎么办」，此时应答线段树（动态开点或离散化），并说明本题因为只有插入且不查询区间和，用有序映射就足够，上线段树属于杀鸡用牛刀。能主动说出「我的 Go 实现插入是 $O(n)$，在 1000 次调用的约束下可接受，但如果调用量上到 $10^5$ 就需要换成平衡树或跳表」，比闭口不谈更能体现工程判断。

易错点总结

错误写法：前驱检查用 prev.end >= start。以 book(10,20) 后再 book(20,30) 为例，prev.end = 20 >= 20 成立，第二次预定被错误拒绝，返回 false，而正确答案是 true。半开区间的首尾相接是合法的，这是本题第一大错误。

错误写法：后继检查用 end >= next.start。以 book(20,30) 后再 book(10,20) 为例，end = 20 >= next.start = 20 成立，被错误拒绝，正确答案是 true。与上一条对称，两处都要用严格大于。

错误写法：只检查前驱，漏掉后继。以 book(10,20) 后再 book(5,15) 为例，起点不超过 5 的区间不存在，前驱检查直接放行，[5,15) 被错误接受；此后日程表里同时有 [5,15) 与 [10,20) 两个重叠区间，book(12,13) 也会因为前驱 [10,20) 被拒——状态已被污染，后续结果全不可信。

错误写法：先 put 写入再做冲突检查，失败时删除。以 book(10,20) 后再 book(10,15) 为例，put(10, 15) 会直接覆盖掉已有的 [10,20)（键相同），即便随后删除也无法恢复原值，日程表凭空少了一个已接受的预定。有序映射按起点做键时，这种写法会静默丢数据。

错误写法：取到 floorKey 或 ceilingKey 后不判空就取值。以第一次调用 book(10,20) 为例，空表上 map.floorKey(10) 返回 null，直接 map.get(prevStart) 得到 null 再拆箱比较，抛 NullPointerException；Go 侧对应的是 l - 1 为 -1 时访问 c.intervals[-1] 触发下标越界 panic。判空必须写在比较之前，靠短路求值保护。

错误写法：Go 二分的判定条件写成 c.intervals[mid][0] <= start。以已有 [[10,20)] 再 book(10,15) 为例，二分会把 l 推到 1，前驱检查的是 l-1 = 0 即 [10,20)，20 > 10 成立仍能拒绝——但换成已有 [[10,20)] 再 book(10,10) 这类退化输入，边界语义已经偏移，l 的含义不再是「第一个起点 ≥ start 的位置」，后继检查会跳过本该检查的区间。二分的判定式必须严格对应你想要的那个下界语义。

错误写法：Go 侧插入直接 append 到切片尾部，不做搬移。以 book(20,30) 后再 book(5,10) 为例，切片变成 [[20,30),[5,10)]，不再有序；下一次 book(6,8) 的二分会在无序数组上给出错误的 l，把明显重叠的预定判为通过，返回 true，正确答案是 false。

错误写法：Go 侧用 copy(c.intervals[l:], c.intervals[l+1:]) 做搬移（方向写反）。以已有 [[10,20),[30,40)] 再 book(0,5) 为例，本应把两个元素右移，实际却把后面的元素左移覆盖了前面，切片内容变成 [[0,5),[30,40),[30,40)]，丢失了 [10,20)，之后 book(15,16) 会被错误接受。右移必须从后往前拷贝，copy 的源和目标区间要写成 copy(dst[l+1:], src[l:])。

错误写法：把冲突条件直接写成通用式但取错方向，如 max(a,c) <= min(b,d)。以 [10,20) 与 [20,30) 为例，$\max(10,20) = 20$，$\min(20,30) = 20$，20 <= 20 成立被判为重叠，返回 false，正确答案是 true。通用式必须是严格小于。

错误写法：以为 end 也需要单独二分定位一次。以 book(10,50) 在已有 [[20,30)] 时为例，只查 start = 10 的前驱后继：后继是 [20,30)，50 > 20 成立，正确返回 false。多做一次基于 end 的二分不会改变结果，却会让两处下标语义交叉，实现中极易把 l 和另一个下标用混。本题一次二分足矣。

错误写法：Java 里把 Integer 与 int 混用做比较，如 if (prevStart != null && map.get(prevStart) > start) 写成 map.get(prevStart).equals(start) 之类。以 book(10,20) 后 book(20,30) 为例，equals 比较的是相等而非大小，前驱检查完全失效，任何重叠预定都会被放行。

相似题目

题目	难度	考察点
732. 我的日程安排表 III	困难	允许任意重叠，要返回最大重叠层数，需差分计数或动态开点线段树
56. 合并区间	中等	一次性给全部区间，排序后线性合并，是离线版本而非在线设计
57. 插入区间	中等	插入时不拒绝而是与相交区间合并，重点在三段式扫描的边界拼接
435. 无重叠区间	中等	目标从「能否插入」变成「最少删几个」，需按右端点贪心
253. 会议室 II	中等	允许重叠但要算最少房间数，用最小堆维护正在进行的会议结束时间
252. 会议室	简单	只判断全体是否两两不重叠，排序后比较相邻两项即可，是本题的静态简化版
986. 区间列表的交集	中等	求两个有序区间列表的全部交集，用双指针同时推进而非二分查找
1288. 删除被覆盖区间	中等	判定的是包含关系而非相交，排序时右端点要降序才能一次扫完
LCR 058. 我的日程安排表 I	中等	与本题同题，可直接套用同一套前驱后继检查