区间覆盖题解

思路

设已经连续覆盖到位置 $x$。为了用尽量少的区间继续覆盖，应在所有满足 $L_i\le x$ 的候选区间中选择右端点最大的一个，使一次选择后的覆盖范围尽可能远。

目标区间是闭区间，因此两个区间在端点处相接时没有空隙，可以连续覆盖。特别地，当 $S=T$ 时仍需选择一个包含该点的区间。

做法

将所有区间按左端点从小到大排序。令当前连续覆盖位置为 $S$，扫描所有左端点不大于当前位置的区间并记录最大右端点。第一次必须选择一个包含 $S$ 的区间；以后每次都要求最大右端点严格超过当前位置，否则无法继续覆盖。选择后将当前位置更新为该最大右端点，直到达到或越过 $T$。

证明贪心正确。设某一步当前覆盖到 $x$，任意可行方案下一步选择的区间右端点为 $r$，贪心选择的右端点为 $r'\ge r$。用贪心区间替换该方案的下一段后，已经覆盖的范围只会扩大，不会增加后续所需区间数量。逐步交换即可得到一个与贪心选择一致且区间数不多于任意最优方案的解。

复杂度

排序需要 $O(n\log n)$ 时间，扫描需要 $O(n)$ 时间，总时间复杂度为 $O(n\log n)$；空间复杂度为 $O(n)$。