$1、区间合并: 按左端点排序$
$判断当前最大右端点与下一个区间左端点的关系$
AcWing 803. 区间合并
$2、区间选点: 按右端点排序$
$判断当前最大右端点与下一个区间左端点的关系$
AcWing 905. 区间选点
$3、最大不相交区间数量: 与区间选点一样$
$因为最大不相交区间点数==最小覆盖区间点数$
AcWing 908. 最大不相交区间数量
$4、区间分组:$
AcWing 906. 区间分组
$做法一:看成教室举行活动,在高峰期需要几间教室$
$代码:$
//相当于举行不同的活动的时间不能有重叠
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=200010;
int cnt;
struct Edge
{
int l,flag;
bool operator<(const Edge& s)const
{
if(l!=s.l) return l<s.l;
else return flag<s.flag;
}
}edge[N];
int n;
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int l,r;
cin>>l>>r;
edge[cnt++]={l,0};
edge[cnt++]={r,1};
}
sort(edge,edge+cnt);
int sum=0;
int res=0;
for(int i=0;i<cnt;i++)
{
if(edge[i].flag==0) sum++; //有活动开始
else sum--; //有活动结束
res=max(res,sum);
}
cout<<res;
return 0;
}
$做法二:$
$按左端点排序 $
$用小根堆存储右端点的值,每次将最小的右端点的值和新区间左端点的值进行比较$
$5。区间覆盖:按左端点进行排序$
$从前往后枚举每个区间,在所有能覆盖start的区间中,$
$选择右端点的最大区间,然后将start更新成右端点的最大值$