题目重点：按开始时间有序维护已接受预约，只需检查插入位置前后邻居；解释 Python list 插入并非 O(log n)。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练 book(start,end) 尝试预约半开区间，要求 start<end；与已接受预约正时长重叠则返回 False，不写入。
- 两个区间仅在端点相接可并存，如 [10,20) 和 [20,30)。
- 单线程进程内结构；并发多副本预约要用共享权威事务约束。
解题路线
- 维护按 start 升序且两两不重叠的 starts/ends。用 bisect_left 找新 start 的插入位置 i。
- 只有前邻居可能从左覆盖新 start、后邻居可能从右落入新 [start,end)；检查 prev.end>start 和 next.start<end。
- 若都不冲突，在 i 插入开始/结束。前后均无重叠则由于现有区间本就有序不重叠，新预约也保持不变量。
- 若语言有平衡树可 O(log n) 找邻居和插入；Python list 的二分是 O(log n)，元素挪动插入仍 O(n)。
手动走一遍
已预约 [10,20)、[30,40)。新 [20,30) 与两侧仅端点相接，成功；[19,21) 与左侧冲突，失败；[25,35) 与右侧冲突，失败。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Half-open nonoverlapping interval calendar with sorted start times."""
from bisect import bisect_left
class MyCalendar:
def __init__(self):
self.starts = []
self.ends = []
def book(self, start: int, end: int) -> bool:
if start >= end:
raise ValueError("nonempty half-open interval required")
index = bisect_left(self.starts, start)
if index > 0 and self.ends[index - 1] > start:
return False
if index < len(self.starts) and self.starts[index] < end:
return False
self.starts.insert(index, start)
self.ends.insert(index, end)
return True
复杂度
n 个预约：Python list 查询位置 O(log n)，插入 O(n) 最坏、存储 O(n)；若用平衡搜索树可把插入降至 O(log n)。
易错点与追问
容易失分的边界
- 把相接端点当冲突，混淆闭区间与半开区间。
- 只检查前邻居，漏掉右邻居冲突。
- Python list 做二分后就声称 book 总 O(log n)。
- 失败预约也被插入，破坏不变量。
继续深挖
- My Calendar II 允许最多两重预约时邻居检查为什么不够？
- 并发两用户预约同一时段如何保持原子性？
- 支持取消/查询空档时怎样扩展？
