AcWing 803. 区间合并

/*贪心
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
pair<int,int> a[N];
int n,num;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].first>>a[i].second;
    sort(a+1,a+1+n);
    num=n;
     for(int i=1;i<n;i++)
        {
            if(a[i].second>=a[i+1].first)
            num--;
            a[i+1].first=a[i].first;
            a[i+1].second=max(a[i+1].second,a[i].second);
        }
    cout<<num;
    return 0;
}
*/
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n;
typedef pair<int,int> PII;
vector<PII> segs;
void merge(vector<PII> &segs){
    vector<PII> res;
    sort(segs.begin(),segs.end());
    int st=-2e9,ed=-2e9;
    for(int i=0;i<n;i++){
        if(ed<segs[i].first){
            if(st!=-2e9) res.push_back({st,ed});
            st=segs[i].first,ed=segs[i].second;
        }
        else ed=max(ed,segs[i].second);
    }
    if(st!=-2e9) res.push_back({st,ed});
    segs=res;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int l,r;
        cin>>l>>r;
        segs.push_back({l,r});
    }
    merge(segs);
    cout<<segs.size()<<endl;
    return 0;
}

AcWing 803. 区间合并