区间问题大纲（贪心）

 前置文章：DP vs 贪心：石子合并 与 合并果子

 

目录

一、区间选点

二、最大不相交区间数量

三、区间分组

四、区间覆盖

---

本篇以下罗列区间问题均为贪心

一、区间选点

​​​​​该问题是“单峰函数”每次选择局部最优解即可找到全局最优解

 

 ①可证明选出来的区间无交集、且数量为最大值

②从小于总数量角度易证

#include<iostream>
#include<algorithm>
using namespace std;const int N = 100010;
int n;
struct Range//运算符重载不一定非要在class中定义对象用
{int l, r;bool operator< (const Range &w)const//常量化、引用 Range类型的w，{//最后的const表示该函数不会修改类的成员变量（如果是类的成员函数的话）。return r < w.r;//为sort函数准备排序依据}
}range[N];int main()
{cin>>n;for (int i = 0; i < n; i ++ ){int l, r;cin>>l>>r;range[i] = {l, r};//range的元素是个结构体，和动态规划的区别也在此}sort(range, range + n);//排序数组下标0到下标n-1（包括第n-1个）元素，根据重载的<运算符定义来比较struct对象间大小int res = 0, ed = -2e9;for (int i = 0; i < n; i ++ )if (range[i].l > ed)//如果 当前区间左端点 比 上一个最大的区间右端 大的话那么就需要新选择点res++{res ++ ;ed = range[i].r;//当前区间右端点重新设置为最大区间范围右端点（变为 上一个最大的区间右端点）}cout<<res;return 0;
}

二、最大不相交区间数量

 本题与上一题流程、代码基本相同

三、区间分组

 

①如上面三个线段分出来两组可证

②按照左端点排序，遍历到L[i]区间，前i-1区间左端点都是小于L[i]左端点的，假设前i-1区间都有重叠部分也就是此时cnt至少为i，且L[i].l<组.r_max那么往后肯定ans>=cnt

用堆来动态维护每组r最小值

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>using namespace std;const int N=100010;
int n;struct Range
{int l, r;bool operator<(const Range &w) const{return l < w.l;}
}range[N];int main()
{cin>>n;for (int i = 0; i < n; i++){int l, r;cin>>l>>r;range[i] = {l, r};}sort(range, range + n);priority_queue<int, vector<int>, greater<int>> heap;for (int i = 0; i < n; i++){auto r = range[i];if (heap.empty() || heap.top() >= r.l)heap.push(r.r);else{int t = heap.top();heap.pop();heap.push(r.r);}}cout<<heap.size();return 0;
}

按左端点排序还是按右端点排序目前没有一个很好的总结，这也是贪心问题的难点。

四、区间覆盖

 

 

 1.所有区间按左端点从小到大排序

 2.从前往后依次枚举每个区间，在所有能覆盖start的区间中，选择右端点最大的区间，让后将start更新为该右端点作为右端点最大值。

ans是最优解，假设cnt是算法没找到的情形反证，得到算法一定不会算出cnt比如上图应该为4个区间却有5个这种情况。因为算法过程会进行自身调整。

本题代码要稍微注意一下内部流程的处理技巧

#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;int n;
struct Range
{int l, r;bool operator< (const Range &W)const{return l < W.l;}
}range[N];int main()
{int st, ed;//指定区间的start endcin>>st>>ed;cin>>n;for (int i = 0; i < n; i ++ ){int l, r;cin>>l>>r;range[i] = {l, r};}sort(range, range + n);int res = 0;bool success = false;for (int i = 0; i < n; i ++ )//i从第一个区间向后枚举{int j = i, r = -2e9;//j从上一轮最后一个区间向后枚举while (j < n && range[j].l <= st){r = max(r, range[j].r);//过程记录右端点修改为“较大值”j ++ ;}if (r < st)//本轮右端点比上一轮的右端点要小，那没结果{res = -1;break;}res ++ ;if (r >= ed){success = true;break;}st = r;//本轮作为相对下一轮来讲的上一轮，右端点st用本轮的右端点替代。i = j - 1;}if (!success) res = -1;cout<<res;return 0;
}