实现一个
MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。
当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。
日程可以用一对整数
startTime 和 endTime 表示，这里的时间是半开区间，即 [startTime, endTime), 实数 x 的范围为， startTime <= x < endTime 。实现
MyCalendar 类：MyCalendar()初始化日历对象。
boolean book(int startTime, int endTime)- 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回
true。
否则，返回
false ，并且不要将该日程安排添加到日历中。示例：
这道题的本质是动态维护一组区间，并在每次插入新区间时判断它是否和已有区间重叠。
这里区间是半开区间：[start, end)，这意味着
end 这个时间点不属于事件本身。所以[10, 20) 和 [20, 30) 这两个事件不重叠，可以同时存在。两个半开区间
[s1, e1) 和 [s2, e2) 不重叠，只有两种情况：- e1 <= s2 # 第一个完全在第二个左边
- e2 <= s1 # 第二个完全在第一个左边
反过来，如果两种情况都不成立，就说明它们有交集。
解法一：线性扫描 —— 每次和所有已有事件比较
最直观的做法是维护一个列表
calendar，里面存所有已经成功预订的事件。每次来了一个新区间 [start, end)，我们就遍历已有事件，检查是否重叠。如果存在某个已有区间
[s, e)，满足 start < e and s < end，就说明两个区间重叠，不能插入。为什么这个条件成立？因为它等价于“新区间不是完全在旧区间左边，也不是完全在旧区间右边”。换句话说，只要两个区间互相越过了对方的起点，就产生了交集。
这个解法在日历规模不大时，直接拿新区间和所有旧区间比一遍就够了。它不依赖额外复杂数据结构，
Walk Through Example
假设当前已经有
[10, 20)，现在尝试插入 [15, 25) 。因为 15 < 20，并且 10 < 25，两个区间发生重叠，所以返回 False。如果尝试插入
[20, 30)， 由于新区间的 start == 20，刚好等于旧区间的 end，两个半开区间不重叠，因此可以插入，返回 True。复杂度分析
设当前已经成功预订了
n 个事件。- 时间复杂度：
每次
book 的时间复杂度是 O(n)，因为最坏情况下需要检查所有已有事件。如果总共有
n 次预订操作，那么整体时间复杂度是 O(n^2)。- 空间复杂度是
O(n)，用于保存所有成功预订的事件。
解法二：排序列表 + 二分 —— 只检查相邻区间
线性扫描的问题是每次都要检查所有已有事件。但如果我们始终让事件按开始时间排序，就不需要看所有事件。
原因是：对于一个新区间
[start, end)，如果它会和某个已有区间重叠，那么最有可能发生冲突的只有两个邻居：- 插入位置右边的第一个区间；
- 插入位置左边的最后一个区间。
为什么只看邻居就够了？
因为区间已经按开始时间排序，并且已有区间之间本来互不重叠。新区间插入后，如果它不和左邻居、右邻居重叠，那它也不可能越过这些邻居去和更远的区间重叠。
所以流程是：
- 先用二分找到新区间按
start应该插入的位置idx。
- 然后检查：
- 右邻居是否满足
end > right_start； - 左邻居是否满足
left_end > start。
只要有一个成立，就说明重叠。
复杂度分析
- 时间复杂度
每次查找插入位置是
O(log n)。但 Python list 在中间插入是
O(n)，所以每次 book 的总时间复杂度是 O(n)。如果语言里有真正的平衡树结构，比如 Java 的
TreeMap、C++ 的 set，或者 Python 第三方库 SortedList / SortedDict，则查找和插入都可以做到 O(log n)。- 空间复杂度是
O(n)。
解法三：有序集合 / SortedDict —— 用平衡树维护区间
如果使用有序集合，我们可以让插入和查找都保持
O(log n)。一种常见设计是按事件的结束时间
end 排序，存储：当要插入新区间
[start, end) 时，我们只需要找第一个：这表示这个已有事件不是完全在新区间左边，它是第一个可能和新区间重叠的事件。
如果这个事件的
start < end，那么它和新区间有重叠，返回 False。否则，新区间可以插入。这个解法的 intuition 是：按结束时间排序后，所有
end <= start 的事件都安全地在新区间左侧，不可能冲突。第一个 end > start 的事件，是唯一需要检查的候选冲突。复杂度分析
设当前已经成功预订了
n 个事件。- 时间复杂度：每次
book的时间复杂度是O(log n)，因为有序集合支持对数级查找和插入。
- 空间复杂度：
O(n)，用于保存所有事件。
注意：这份代码依赖
sortedcontainers，LeetCode Python 环境通常支持。 解法四：手写二叉搜索树 —— 把区间放进 BST
如果没有现成的有序集合，也可以自己维护一棵二叉搜索树。每个节点存一个区间
[start, end)插入新区间时，和当前节点比较：
- 如果
start >= cur.end，说明新区间完全在当前区间右边，去右子树；
- 如果
end <= cur.start，说明新区间完全在当前区间左边，去左子树；
- 否则，说明两个区间重叠，插入失败。
这个逻辑和普通 BST 插入很像，只不过比较依据不是单个值，而是区间相对位置。
树里的每个节点都代表一个已经预订成功的事件。对于某个节点
[s, e)：- 左子树中的所有事件都应该完全在它左边；
- 右子树中的所有事件都应该完全在它右边。
这样一来，插入新区间时，只要不断和当前节点比较，就能决定应该往左走、往右走，还是发现重叠直接失败。
复杂度分析
- 时间复杂度：
每次插入的时间复杂度取决于树高。
如果树比较平衡，每次
book 平均是 O(log n)。但这棵树不是自平衡 BST，最坏情况下会退化成链表，比如事件按递增顺序插入时，时间复杂度会变成
O(n)。- 空间复杂度是
O(n)，每个成功预订的事件对应一个树节点。
总结
方法 | 每次 book 时间 | 空间 | 适合场景 |
线性扫描 | O(n) | O(n) | 最简单，约束小，最容易写对 |
排序列表 + 二分 | 查找 O(log n)，插入 O(n) | O(n) | Python list 写法简洁，但插入仍是线性 |
有序集合 / 平衡树 | O(log n) | O(n) | 语言支持 TreeMap / set / SortedDict 时最优雅 |
手写 BST | 平均 O(log n)，最坏 O(n) | O(n) | 不依赖库，但不是严格平衡树 |
这题本质是维护一组互不重叠的半开区间
[start, end)。判断两个区间是否重叠，可以用条件 start < old_end and old_start < end。最简单的做法是每次遍历所有已有事件，如果有重叠就返回 False，否则插入新区间，时间复杂度是 O(n)。如果想优化，可以保持事件有序。按开始时间排序后，新区间只可能和插入位置左右两个邻居冲突，所以可以二分找到插入位置并检查相邻区间。在 Python list 里，二分查找是
O(log n)，但插入仍然是 O(n)；如果用真正的有序集合或平衡树，就可以做到每次 O(log n)。还有一种不依赖库的写法是手写二叉搜索树。每个节点存一个区间。插入新区间时，如果它完全在当前区间右边，就去右子树；如果完全在当前区间左边，就去左子树；否则说明重叠，返回
False。这个方法平均表现接近 O(log n)，但因为不是自平衡树，最坏会退化到 O(n)。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-729-日程安排-1
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 560] 和为 K 的子数组
下一篇
[Leetcode 772] 基础计算器 III