区间合并

作用：快速将几个有交集的区间合并成一个区间

方法：

按区间左端点排序
从左到右扫描区间：

若当前区间与后面的区间都没有交集，记录答案

若当前区间包含下一个区间，继续判断后面

若当前区间与下一个区间相交，则当前区间的右端点变为下个区间的右端点

不难发现，后两种情况可以合并成当前区间的右端点变为当前右端点和下一个区间右端点的最大值。

例：给定$n$个区间$[l_i,r_i]$，合并区间，输出合并后区间的个数

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

typedef pair<int,int> PII;
const int N=1e5+5;
int n;
PII a[N];
vector<PII>ans;

void merge(){
    sort(a+1,a+n+1);
    int s=-2e9,t=-2e9;
    for(int i=1;i<=n;i++){
        if(t<a[i].first){
            if(t!=-2e9)ans.push_back({s,t});
            s=a[i].first,t=a[i].second;
        }
        else{
            t=max(t,a[i].second);
        }
    }
    if(s!=-2e9)ans.push_back({s,t});
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        int l,r;
        cin >> l >> r;
        a[i]={l,r};
    }
    merge();
    cout << ans.size();
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。