AcWing 905. 区间选点
原题链接
简单
作者:
Anoxia_3
,
2020-01-26 22:35:05
,
所有人可见
,
阅读 1016
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
struct node{
int l,r,me;
}s[N];
bool cmpl(node a , node b){
return a.l<b.l;
}
bool cmpr(node a , node b){
if(a.r<b.r || a.r==b.r&&a.l<b.l) return true;
else return false;
}
bool flag[N];
int main(){
int k=0;
int n;
cin>>n;
for(int i = 0 ; i<n ; i++) {
cin>>s[i].l>>s[i].r;
s[i].me = i;
}
sort(s,s+n,cmpr);
for(int i = 0 ; i<n ; i++){
if(flag[i]) continue;
k++;
for(int j = i ; j<n ; j++)
if(s[j].l<=s[i].r) flag[j]=true;
}
cout<<k<<endl;
return 0;
}