行业知识
【C++算法】贪心算法-区间问题,超详细注释例题讲解
2026-11-18 02:40:17
来源:互联网转载
文章目录
- 1)最大不相交区间数(区间选点)
- 2)区间分组
- 3)区间覆���
以下例题来自于AcWing 906~908
1)最大不相交区间数(区间选点)
- 翻译一下题目,也就是说给定 N N N个闭区间,问能从中选出多少个区间使其互不相交
- 贪心策略:新建一个结构体存储区间的左端点和右端点,将这 N N N个区间按照右端点从小到大排序,遍历所有的区间,如果当前遍历到的区间左端点的值大于了上一个区间的右端点的值,说明此时区间没有重合,则区间个数 + 1 +1 +1
#include#define x first#define y secondusing namespace std;typedef long long ll;typedef pair PII;// 解题思路: const int N=1e5+5; // 区间总数// 区间struct Range {int l; // 左端点int r; // 右端点}range[N];// 按照区间右端点从小到大排序bool cmp(Range a,Range b) {return a.rcin>n;// 输入规模大于1e5,推荐使用速度更快的scanffor(int i=1;iscanf("%d%d",&range[i].l,&range[i].r);}// 计算答案int res=0;int front_r=INT_MIN; // i=1时至少有一个,所以res从0开始sort(range+1,range+1+n,cmp); // 排序for(int i=1;iif(range[i].lfront_r) {res++;front_r=range[i].r; // 更新上一个区间的右端点}}cout 某一分组最大右端点- 如果存在这样的分组(与某个分组间没有交集),则将区间 $ i $ 放进去,并且更新这个分组的最大右端点(注意,如果与多个分组都有交集则可以放到任意一个分组中,不影响结果,可自行模拟证明)
- 如果不存在这样的分组(与每个分组间都有交集),则开一个新组,再把区间 i i i 放进去
- 在判断当前区间是否与某一分组有交集时,只需要与所有分组中最小的分组最大右端点进行比较即可,因为这是最有可能满足 r a n g e [ i ] . l > 某一分组最大右端点 range[i].l \ > \ 某一分组最大右端点 range[i].l > 某一分组最大右端点 的情况,对于所有分组中最小的分组最大右端点,只需要用一个小根堆来维护即可
#include#define x first#define y secondusing namespace std;typedef long long ll;typedef pair PII;// 解题思路: // 将所有区间按照左端点从小到大排序,从前往后遍历每个区间,判断能否将其放进某个现有的组中// 用堆来维护每个分组的MAX_r,const int N=1e5+5;struct Range {int l;int r;}range[N];bool cmp(Range a,Range b) {// 按照左端点从小到大排序return a.lint n;cin>n;for(int i=1;iint l,r;scanf("%d%d",&l,&r);range[i]={l,r};}sort(range+1,range+1+n,cmp);priority_queue// 如果每个分组中最小的MAX_R都比当前区间的左端点大(说明有交集,不能放入该区间中)if(heap.empty() || heap.top()=range[i].l) {heap.push(range[i].r); // 新开一个分组} else {// 如果无交集,说明可以放入该分组中,此时弹出再更新这个分组的最大值heap.pop(); // 因为rnage[i].r一定比heap.top()更大,不然怎么可能无交集heap.push(range[i].r);}}// 小根堆的大小就是分组的个数cout int l,r; // 左端点,右端点 // 重载运算符从小到大排序 bool operator return l int st,en; cinsten; int n; cinn; for(int i=1;i int l,r; scanf("%d%d",&l,&r); range[i]={l,r}; } sort(range+1,range+1+n); int res=0; // 存储答案 bool success=false; // 遍历所有区间 for(int i=1;i // front_r可理解为当前覆盖到的区域 int j=i,front_r=INT_MIN; // 双指针,j从第i个区间开始找 // 取所有左端点能覆盖st中右端点最大的区间,覆盖到这个位置 while(j front_r=max(front_r,range[j].r); j++; } // 如果front_r仍小于st,说明线段不可被已有区间覆盖 if(front_r break; } // 如果找得到,答案+1 res++; // 已经完全覆盖 if(front_r=en) { success=true; break; } // 否则更新i和j st=front_r; // 迭代st,后面的区间继续和st比 i=j-1; // 双指针,加速遍历 } if(!success) res=-1; cout