动态合并区间并查询最大区间长度
哪些公司问过
答案要点
- 有序集合按左端点维护互不相交的区间
- 插入时定位前驱,再向右收集所有相交区间并删除合并
- 多重集合或带延迟删除的堆维护区间长度
- 每个区间最多插入删除一次,插入均摊 O(log n)
- 查询最大长度取长度集合最大值,O(1) 或 O(log n)
易错点
- 只检查后继,漏掉与左侧前驱区间的相交
- 合并后忘记在长度集合中删除旧长度
- 用普通 set 存长度,长度相同的区间互相覆盖
面试官常见追问
- 端点相邻但不重叠,比如 [1,3] 和 [4,5] 要不要合并?
- 如果用堆维护长度,删除怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。