AcWing 905. 区间选点
原题链接
简单
作者:
牛奶小柒Luke
,
2021-03-02 00:36:48
,
所有人可见
,
阅读 188
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 100010;
struct range{
int l,r;
}seg[N];
bool cmp(const range &a,const range &b){
return a.r < b.r;
}
int n;
int main(){
scanf("%d",&n);
for(int i = 0;i < n;++i) scanf("%d%d",&seg[i].l,&seg[i].r);
sort(seg,seg + n,cmp);
LL cnt = 0;
int last = -2e9;
for(int i = 0;i < n;++i){
if(last < seg[i].l){
cnt++;
last = seg[i].r;
}
}
printf("%lld",cnt);
return 0;
}