AcWing 905. 区间选点
原题链接
简单
作者:
minux
,
2020-05-04 14:41:09
,
所有人可见
,
阅读 464
#include <bits/stdc++.h>
using namespace std;
const int INF=-1e9-5;
const int N=1e5+5;
int n;
struct Range{
int l, r;
bool operator< (const Range& o) const{
return r<o.r;
}
}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);
int res=0;
int END=INF;
for(int i=0; i<n; ++i){
if(range[i].l>END){
++res;
END=range[i].r;
}
}
cout<<res<<endl;
return 0;
}