贪心

左端点排序

1. 对每个区间左端点排序
2. 从前往后枚举每个区间
   1. 若l_i<=r，缩小维护的区间（交集思路）
   2. 否则，更新l_i,r_i为当前维护的区间，选点数 +1

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
int n;
vector<PII> segs;
int merge(){
    int l=-2e9,r=-2e9,cnt=0;
    sort(segs.begin(),segs.end());//左端点排序
    for(auto seg: segs){
        if(seg.first<=r){//缩小区间
            l=max(l,seg.first);
            r=min(r,seg.second);
        }
        else{
            cnt+=1; //模拟样例发现，先选点，再缩小区间
            l=seg.first;
            r=seg.second;
        }
    }
    return cnt;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        segs.push_back({l,r});
    }
    printf("%d\n",merge());
}

右端点排序

1. 对每个区间右端点排序
2. 从前往后依次枚举每个区间
   1. 若区间包含点，则跳过
   2. 否则 选择当前区间的右端点
3. 证明：
   （1）上述选法必然会使每个区间里至少包含一个点，是一种合法方案，所以ans<=cnt（这里的ans是最优解）
   （2）对于ans≥cnt的证明：由贪心策略可知，贪心方法将会选择尽量少的点覆盖所有的区间，且每个点对应的区间的集合不相交；使用反证法，不妨假设ans<cnt成立，由于ans是最优解，那么ans个点也覆盖所有的区间，即存在更少的点ans可以覆盖所有的区间。这与贪心策略不符，因为一旦有更少的点可以覆盖所有的区间，那么它一定是贪心解cnt，否则更少的点不能覆盖所有的区间，与假设矛盾。因此ans≥cnt成立

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
int n;
vector<PII> segs;
int merge(){
    int l=-2e9,r=-2e9,cnt=0;
    //右端点排序
    sort(segs.begin(),segs.end(),[](const PII&a,const PII& b){
        return a.second<b.second;
    });
    for(auto seg: segs){
        //选择的右端点不在当前区间内，重新选择
        if(r<seg.first){
            r=seg.second;
            cnt+=1;
        }
    }
    return cnt;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        segs.push_back({l,r});
    }
    printf("%d\n",merge());
}