区间贪心做法还是比较单一的，一共三种情况
左端点排序、右端点排序，多关键字排序
区间选点
按右端点排序，在每一段区间中靠右边的点是最优的，因为越靠右边的点就越有可能覆盖更多的区间
证明过程可以用夹逼定理进行证明，假定最终的最小值是ans，统计出来的数量是num，证明ans>=num且ans<=num，就可以证明ans==num
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct sa
{
int l;
int r;
}range[N];
int cmp(const sa &a,const sa &b)
{
return a.r<b.r;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) scanf("%d%d",&range[i].l,&range[i].r);
sort(range,range+n,cmp);
int res=0,ed=-(1e9+10);
for(int i=0;i<n;i++)
{
if(range[i].l>ed)
{
res++;
ed=range[i].r;
}
}
cout<<res<<endl;
return 0;
}
最大不相交区间数量
和这道题一样的模型之前遇到过几个，比如：一个人要去看表演，每个给出每个表演的时间，问怎么能看到最多的节目
这道题和上道题是完全一样的！代码也是一样的！
区间分组
先按左端点从小到大排序
对于每一组，如果所有组一组最右边的右端点大于当前区间的左端点，那么说明有交集，需要重新建立一个组
这里用小根堆维护每一组最右边的右端点，每次取出最小的最右端点，如果最小的最右端点都无法插入，那么说明整个堆中的最有端点都不行。如果可以划分成一组，那么就只需要更新当前区间的最右端点值即可
证明过程同样可以用夹逼定理进行证明，假定最终的最小值是ans，统计出来的数量是num，证明ans>=num且ans<=num，就可以证明ans==num
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct sa
{
int l,r;
}range[N];
int cmp(const sa &a,const sa &b)
{
return a.l<b.l;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) scanf("%d%d",&range[i].l,&range[i].r);
sort(range,range+n,cmp);
priority_queue<int,vector<int>,greater<int> >vis;
for(int i=0;i<n;i++)
{
if(vis.empty()||vis.top()>=range[i].l) vis.push(range[i].r);
else
{
int t=vis.top();
vis.pop();
vis.push(range[i].r);
}
}
cout<<vis.size()<<endl;
return 0;
}
区间覆盖
先按左端点从小到达大排序
每一次选取能覆盖掉st的右端点最靠右的区间，然后将st更新成右端点，循环得到解
如果当前没有区间能覆盖到st，则无解
如果循环到最后没能覆盖掉en，则无解
对于这个做法的证明可以直接证答案
对于答案都可以通过这个算法在区间数目不发生变化的情况下转化成算法可以算出的答案
这样算法的正确性就得到了证明
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct sa
{
int l,r;
}range[N];
int cmp(const sa &a,const sa &b)
{
return a.l<b.l;
}
int main()
{
int st,en;
cin>>st>>en;
int n;
cin>>n;
for(int i=0;i<n;i++) scanf("%d%d",&range[i].l,&range[i].r);
sort(range,range+n,cmp);
int res=0;
for(int i=0;i<n;i++)
{
int j=i,r=-(1e9+10);
while(j<n&&range[j].l<=st)
{
r=max(r,range[j].r);
j++;
}
if(r<st)
{
cout<<"-1"<<endl;
return 0;
}
res++;
if(r>=en)
{
cout<<res<<endl;
return 0;
}
st=r;
i=j-1;
}
cout<<"-1"<<endl;
return 0;
}
