等同于线段覆盖
转化题意:给n条线段的左右端点,选出若x条线段能互不相交
贪心的思路,我们每次选定右端点最小的线段,然后选取下一个边时,下个边的左端点一定大于上个边的右端点
我们按区间右端点排序,先选中第一条边的右端点,枚举每个区间,如果这个区间的左端点比上一个选中的右端点大,就选它,因为是按右端点排序,所以第一次被枚举到的区间右端点一定是剩下的最小的
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n;const int maxn=5e5+10;
struct node{
int l,r;
}e[maxn];
bool cmp(node a,node b){
if(a.r!=b.r) return a.r<b.r;
return a.l<b.l;
}
int main(){
cin>>n;
for(int i=1;i<=n;++i) cin>>e[i].l>>e[i].r;
sort(e+1,e+1+n,cmp);
int tot=0;
int last=e[1].r;tot=1;
for(int i=2;i<=n;++i)
if(e[i].l>last) last=e[i].r,++tot;
cout<<tot<<endl;
return 0;
}