面试题库 › 客户端 › 用最少的区间片段覆盖整个时间段

用最少的区间片段覆盖整个时间段

难度 ★★☆在 2 场真实面经中被问到 方向:客户端考点:贪心与回溯

哪些公司问过

BIGO1钉钉1

常见岗位:客户端、C++ / Qt 客户端

答案要点

  1. 按左端点排序,维护当前已覆盖到的位置 cur
  2. 每轮在左端点不超过 cur 的区间中选右端点最远的一个
  3. 最远右端点不超过 cur 时说明存在空洞,返回无法覆盖
  4. 贪心正确性可用交换论证说明,复杂度 O(n log n)
  5. 边界:区间开闭、相接是否算连续、片段超出目标范围

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题