判断日程是否冲突的数据结构设计
哪些公司问过
答案要点
- 重叠条件:新.start < 旧.end 且 新.end > 旧.start
- 批量判断:按开始时间排序后检查相邻区间,O(n log n)
- 动态插入:平衡树按开始时间有序存储,只检查前驱和后继
- 单次查询与插入 O(log n),空间 O(n)
- 允许重叠计数时用差分数组或线段树
易错点
- 端点相接(一个结束时间等于另一个开始时间)误判为冲突
- 只检查后继,漏掉与前驱的重叠
- 动态场景下每次插入都全量排序,复杂度退化
面试官常见追问
- 为什么只检查前驱和后继就够了?
- 如果要求最多允许两个日程重叠呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。