AcWing 905. 区间选点
思路:
将每个区间按右端点从小到大排序
从前往后依次枚举每个区间,如果当前区间中已经包含,则pass
否则,选择当前区间的右端点
代码如下
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct qujian{
int r,l;
}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 note=-1e9,cnt=0;
for(int i=0;i<n;i++)
{
//如果出现断点,则需要选取下一个区间的右端点;
if(note<qu[i].l)
{
note=qu[i].r;
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}