一、什么是区间覆盖问题
“给你很多区间,让你用最少个数,覆盖一个目标区间”
二、区间覆盖贪心核心思想
按照左端点升序排序,当前要覆盖到 pos,在所有 L ≤ pos 的区间中,选择r 最大的那个。
三、区间覆盖核心代码
structInterval{intl,r;};intcoverMin(vector<Interval>&segs,intL,intR){// 左端点升序排列sort(segs.begin(),segs.end(),[](auto&a,auto&b){returna.l<b.l;});intans=0;intpos=L;inti=0;intn=segs.size();while(pos<=R){intbestR=-1;// 找所有能覆盖 pos 的区间while(i<n&&segs[i].l<=pos){bestR=max(bestR,segs[i].r);i++;}// 无法继续覆盖if(bestR<pos)return-1;ans++;pos=bestR+1;}returnans;}四、什么是区间调度问题
“从一堆区间中,选最多个互不重叠的区间”
五、区间调度贪心核心思想
每次选择:
在所有“起点 ≥ 当前结束时间”的区间中,结束最早的那个。
六、概览
| 维度 | 区间调度 | 区间覆盖 |
|---|---|---|
| 目标 | 选最多 | 选最少 |
| 要求 | 区间互不重叠 | 覆盖整个目标区间 |
| 排序方式 | 按右端点升序 | 按左端点升序 |
| 贪心策略 | 尽量早点结束 | 尽量覆盖得远 |
| 典型题 | 会议室安排 | 摄像头 / 视频拼接 |
七、例题
区间覆盖:
PG:世界杯只因
LeetCode:跳跃游戏Ⅱ
LeetCode:视频拼接
进阶:(需按照右端点升序排序)
LeetCode:用最少数量的箭引爆气球
区间调度:
洛谷:凌乱的yyy/线段覆盖