思路

1. 合并区间，思路：模拟+贪心
2. 先对区间按左端点进行排序
3. 维护合并的区间[st,ed],再依次遍历区间 i
   1. 若ed > st_i，代表两个区间不能合并，此时 维护的合并区间 变成 区间i
   2. 若 ed_i <= ed，区间能合并，更新维护的区间ed=max{ed,ed_i}
   3. 不存在 st_i < st的情况，因为前面已经排序了，因此 对于 ed >st_i 这种情况，可以确定当前维护的区间[st,ed]后续不会再被使用

#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;
void merge(vector<PII>& segs){
    vector<PII> res;
    int st=-2e9,ed=-2e9;//当前维护的区间
    sort(segs.begin(),segs.end());
    for(auto seg:segs){
        if(ed<seg.first){//2段区间，不能合并
            if(st!=-2e9) res.push_back({st,ed});
            st=seg.first;
            ed=seg.second;
        }
        else{
            ed=max(ed,seg.second);
        }
    }
    if(st!=-2e9) res.push_back({st,ed});
    segs=res;
}
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});
    }
    merge(segs);
    // for(auto tt:segs) printf("%d %d\n",tt.first,tt.second);
    printf("%d",segs.size());
    return 0;
}

题目2：格子染色
1. 可以看成嵌套区间合并，外层是不同行\列的合并，内层是同一行\列的区间合并

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
int n;

//<idx,x,y>：行号/列号、左端点位置、右端点位置
struct Node{
    int idx,x,y;
    bool operator < (const Node& w) const{
        if(idx!=w.idx) return idx<w.idx;
        else if(x!=w.x) return x<w.x;
        else if(y!=w.y) return y<w.y;
    }
};
vector<Node> rows,cols;
LL cnt;
//区间合并
void merge(vector<Node>& segs){
    vector<Node> res;
    sort(segs.begin(),segs.end());
    int st=-2e9,ed=-2e9,idx=-2e9;
    for(auto seg:segs){
        //同一行/列，合并
        if(idx==seg.idx){
            if(ed<seg.x){
                if(st!=-2e9){
                    res.push_back({idx,st,ed});
                    cnt+=ed-st+1;
                }
                st=seg.x,ed=seg.y;
            }
            else ed=max(seg.y,ed);
        }
        //不同行/列，合并
        else{
            if(st!=-2e9){
                res.push_back({idx,st,ed});
                cnt+=ed-st+1;
            }
            //这一行、列已经合并完了，更新行号、列号
            idx=seg.idx;
            st=seg.x,ed=seg.y;
        }
    }
    if(st!=-2e9){
         res.push_back({idx,st,ed});
         cnt+=ed-st+1;
    }
    segs=res;
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        if(x1==x2) cols.push_back({x1,min(y1,y2),max(y1,y2)});
        if(y1==y2) rows.push_back({y1,min(x1,x2),max(x1,x2)});
    }
    merge(cols);

    merge(rows);
    //去重

    for(auto row: rows){
        for(auto col: cols){
            if(row.idx>=col.x && row.idx<=col.y && col.idx>=row.x && col.idx<=row.y) cnt-=1;
        }
    }
    printf("%lld\n",cnt);
    return 0;
}