AcWing 908. 最大不相交区间数量
原题链接
简单
作者:
minux
,
2020-05-04 15:23:13
,
所有人可见
,
阅读 509
#include <bits/stdc++.h>
using namespace std;
const int INF=-1e9-5;
const int N=1e5+5;
struct Range{
int l, r;
bool operator< (const Range &o) const{
return r<o.r;
}
}range[N];
int n;
int main(){
// 贪心策略
cin>>n;
int a, b;
for(int i=0; i<n; ++i){
cin>>a>>b;
range[i]={a, b};
}
sort(range, range+n);
int END=range[0].r;
int cnt=1;
for(int i=1; i<n; ++i){
if(range[i].l>END){
END=range[i].r;
++cnt;
}
}
cout<<cnt<<endl;
return 0;
}