用最少的区间片段覆盖整个时间段
哪些公司问过
答案要点
- 按左端点排序,维护当前已覆盖到的位置 cur
- 每轮在左端点不超过 cur 的区间中选右端点最远的一个
- 最远右端点不超过 cur 时说明存在空洞,返回无法覆盖
- 贪心正确性可用交换论证说明,复杂度 O(n log n)
- 边界:区间开闭、相接是否算连续、片段超出目标范围
易错点
- 按右端点排序或只选左端点最小的区间,得不到最优解
- 没处理中间空洞,导致死循环或返回错误结果
- 相接区间的开闭判断写错
面试官常见追问
- 有没有需要注意的边界问题?
- 为什么不用动态规划?
- 和跳跃游戏 II 有什么关系?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。