题干与适用场景
实现一个日程类，book(start, end) 在不重叠时返回 true 并保存区间，否则返回 false。区间采用半开语义，要求 start < end；例如 [10, 20) 与 [20, 30) 可以相邻。题目考察排序结构、区间边界、插入时机和复杂度，不要求直接实现完整日历产品。
面试官考察点
关键是把重叠条件写成可证明的逻辑：新区间只需检查按起点排序的前驱和后继。强回答会比较线性扫描、平衡树和排序数组，说明插入与查找复杂度，并指出多线程或持久化服务需要额外的原子性和锁。
回答前需要澄清的问题
- 时间是整数还是时间戳，是否允许负数？
- 是否保证
start < end，非法输入如何处理？ - 区间是否严格半开，端点相等是否允许相邻？
- 预订数量和时间范围多大，是否需要取消、查询或重复预订？
- 这是单线程内存题，还是需要跨进程并发与持久化？
30 秒回答框架
我会使用按 start 排序的有序映射。对新区间 [s, e)，找到第一个起点不小于 s 的后继；若后继存在且后继 start < e，则重叠。再检查前驱：若前驱 end > s，则重叠。两者都不冲突时插入。半开区间保证前驱 end == s 或后继 start == e 时可以相邻。查找和插入为 O(log n)，空间 O(n)。
分步深入解答
第一步：定义重叠条件
两个半开区间 [a, b) 与 [c, d) 重叠，当且仅当 a < d && c < b。若按起点排序，检查新区间的直接前驱和后继即可，因为更远的区间结束更早或开始更晚。
第二步：选择有序结构
平衡树或 Java TreeMap 支持按键查找前驱和后继；排序数组查找快但中间插入为 O(n)；每次线性扫描为 O(n)。根据预订规模和操作比例选择，不要只背一个容器名称。
第三步：实现检查与插入
先查后继，再查前驱，确认无冲突后才写入。不能先插入再回滚，因为异常或并发会让中间状态可见。
boolean book(int start, int end) {
if (start >= end) return false;
var next = events.ceilingEntry(start);
if (next != null && next.getKey() < end) return false;
var prev = events.floorEntry(start);
if (prev != null && prev.getValue() > start) return false;
events.put(start, end);
return true;
}第四步：证明边界正确
next.start == end 不重叠，prev.end == start 也不重叠。相同 start 不能覆盖旧区间，因此后继检查会拒绝任何与其相交的 end。若时间范围可能溢出，比较时使用安全整数或时间类型。
第五步：说明复杂度
平衡树查找前驱、后继和插入都是 O(log n)，空间 O(n)。排序数组查找 O(log n) 但插入 O(n)；线性扫描实现简单却不适合大量预订。说明复杂度时要包含拒绝路径。
第六步：扩展并发与持久化
单机内存实现需在检查和插入外加同一把锁，保证原子性。跨进程服务应使用数据库事务、唯一约束或可验证的区间锁；缓存只能辅助读取，不能承担最终冲突判定。
设计取舍与边界
半开还是闭区间
半开区间自然表达相邻时段，长度为 end - start，也减少边界重复。若业务使用闭区间，必须重新定义相邻和粒度，不能混用。
TreeMap 还是区间树
只支持“新增且不允许任何重叠”时，前驱后继足够。若增加重叠查询、取消或按范围统计，区间树或数据库范围索引可能更合适。
落地计划与证据
测试矩阵
覆盖首个区间、完全包含、部分重叠、相邻端点、相同 start、非法空区间、大范围数值和重复请求。每次接受后核对有序不变量。
生产化边界
若接口被多个实例调用，定义事务隔离、冲突错误码、重试幂等键和时区规范。把单线程算法的原子检查迁移为持久化层约束并做并发压测。
常见误区与追问
误区：只检查后继
新区间可能覆盖前驱尾部，必须同时检查前驱的 end。
误区：把端点相等判为冲突
半开区间允许 [10, 20) 与 [20, 30) 相邻，比较符号应保持严格小于和大于。
误区：先插入再发现冲突
检查与写入必须作为一个逻辑原子步骤，避免临时破坏不变量。
追问：如何支持允许两次重叠？
需要维护活动区间计数或扫描线结构，问题已从相邻检查升级为最大重叠数约束。
追问：如何处理并发预订？
单机加锁；多实例使用事务、范围锁或可串行化写入，不能只依赖应用内存。