C++贪心———区间覆盖区间调度

一、什么是区间覆盖问题

“给你很多区间，让你用最少个数，覆盖一个目标区间”

二、区间覆盖贪心核心思想

按照左端点升序排序，当前要覆盖到 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/线段覆盖