CJTX05｜信号连续覆盖 题解

核心算法

按左端点排序，分轮选择“当前能够接上且右端点最远”的区间。

思路推导

设当前已经连续覆盖到 current。扫描所有满足 $l_i\le current$ 的区间，找出其中最大的右端点 farthest：

1. 若 farthest == current，说明没有区间能把覆盖继续向右延伸，输出 -1；
2. 否则选择到达 farthest 的区间，答案加一，并令 current = farthest；
3. 重复直到 current >= L。

正确性说明

当前覆盖到 current 时，任何可行方案的下一段都必须满足左端点不大于 current。贪心选择其中右端点最远的区间 $G$。若某个最优方案选择了另一段 $O$，则 $G$ 覆盖得不比 $O$ 短，用 $G$ 替换 $O$ 不会增加设备数，也不会破坏后续覆盖。逐轮替换即可得到贪心方案。

复杂度

• 时间复杂度：$O(n\log n)$；
• 空间复杂度：$O(n)$。

易错点

• 不能看到一个能接上的区间就立即选择，必须比较同一轮所有候选区间的最远右端点；
• 要检测覆盖停滞，否则会死循环；
• 允许端点相接，因此候选条件是 left <= current。