区间覆盖
用最少的给定区间覆盖目标区间;按左端点排序,每次选择能接上且右端点最远的区间。标签 贪心 / 区间 / 覆盖 / 排序
题目描述
给定目标区间 和 个可用区间 。选择尽量少的可用区间,使它们的并集覆盖 。无解输出 。
端点相接视为可以连续覆盖。
。
题解
按左端点 升序排序。维护当前已经覆盖到的右端点 ,初始 ,答案计数为 。
当 时:
- 扫描所有满足 且尚未扫描过的区间,取其中最大的右端点 ;
- 若 ,说明无法继续向右覆盖,输出 ;
- 否则选择这个区间,答案加一,令 。
正确性:当前已经覆盖 ,任何覆盖方案下一步都必须选择一个左端点不超过 的区间。在这些区间中,右端点最远者能覆盖最多后续位置;用它替换任意其他选择不会使方案变差。因此每一步选择都是安全的。
复杂度
排序为 ,每个区间只被扫描一次,总时间为 ,空间为 。