2025-01-25区间合并

区间合并

主要内容

快速地将一系列区间中有交集（包括端点相交）的区间合并成一个,返回处理后的区间列表。

代码模板

void merge(vector<PII>& segs){
    vector<PII> res;

    sort(segs.begin(),segs.end());//先按照左边界大小从小到大排序

    int st=-2e9,ed=-2e9;
    for(auto seg:segs){
        if(ed<seg.first){
            if(ed!=-2e9) res.push_back({st,ed});
            st=seg.first,ed=seg.second;
        }
        else ed=max(ed,seg.second);
    }

    if(ed!=-2e9) res.push_back({st,ed});//要记得把最后一段区间加到结果里

    segs=res;
}

例题

Acwing区间合并_acwing 区间合并-CSDN博客

// https://blog.csdn.net/m0_51547272/article/details/135909456

/*
比题目严格的测试样例
Input:
5
7 9
2 4
5 6
1 2
7 8

Output:
3
*/

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
typedef pair<int,int> PII;
vector<PII> segs;
int n;

void merge(vector<PII>& segs){
    vector<PII> res;

    sort(segs.begin(),segs.end());//先按照左边界大小从小到大排序

    int st=-2e9,ed=-2e9;
    for(auto seg:segs){
        if(ed<seg.first){
            if(ed!=-2e9) res.push_back({st,ed});
            st=seg.first,ed=seg.second;
        }
        else ed=max(ed,seg.second);
    }

    if(ed!=-2e9) res.push_back({st,ed});//要记得把最后一段区间加到结果里

    segs=res;
}

void work(){
    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;
}

int main(){
    work();
    return 0;
}