acwing908. 最大不相交区间数量

分析

要将n个区间化为不相交的区间，先将区间按r排序，然后每次遍历，如果l比当前ed小，那么更新ed，结果+1。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;

struct Range{
    int l,r;
    bool operator<(const Range &w)const{
        return r<w.r;
    }
}range[N];
int n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>range[i].l>>range[i].r;
    sort(range,range+n);
    int res=0,ed=-2e9;
    for(int i=0;i<n;i++){
        if(ed<range[i].l){
            res++;
            ed=range[i].r;
        }
    }
    cout<<res<<endl;
    
    return 0;
}