算法1 以右端点排序

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
vector<PII> alls;
int ans=1;
bool cmp(PII x,PII y){
    return x.second<y.second;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        alls.push_back({l,r});
    }
    sort(alls.begin(),alls.end(),cmp);
    for(int i=1,j=0;i<alls.size();i++){
        if(alls[i].first>alls[j].second){
            ans++;
            j=i;
        }
    }
    printf("%d\n",ans);
    return 0;
}

算法2 以左端点排序

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
vector<PII> alls;
int ans=1;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        alls.push_back({l,r});
    }
    sort(alls.begin(),alls.end());
    for(int i=1,j=0;i<alls.size();i++){
        if(alls[i].first>alls[j].second){
            ans++;
            j=i;
        }else{
            if(alls[i].second<alls[j].second) j=i;
        }
    }
    printf("%d\n",ans);
    return 0;
}