题目
给定N个闭区间[ai,bi],请你在数轴上选择若干区间,使得选中的区间之间互不相交(包括端点)。
输出可选取区间的最大数量。
分析
与区间选点类似,废话不多说,直接上代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct qujian{
int l,r;
}qu[N];
bool cmp(struct qujian a,struct qujian b)
{
return a.r<b.r;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>qu[i].l>>qu[i].r;
}
sort(qu,qu+n,cmp);
int cnt=0;
int e=-1e9;
for(int i=0;i<n;i++)
{
if(e<qu[i].l)
{
cnt++;
e=qu[i].r;
}
}
cout<<cnt;
return 0;
}