无重叠区间:最少移除几个区间(LC435)
哪些公司问过
答案要点
- 转化为求最多不重叠区间数,答案=总数-最大保留数
- 按右端点升序排序,优先保留结束最早的区间
- 左端点≥上一个保留区间的右端点才算不重叠
- 正确性可用交换论证说明
- 时间O(n log n)
易错点
- 端点相接也当成重叠,用了严格大于
- 按左端点排序却不处理重叠时保留哪个
- 直接返回保留数而不是移除数
面试官常见追问
- 为什么按左端点排序直接贪心可能出错?
- 和用最少的箭引爆气球(LC452)有什么区别?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。