区间合并

区间合并

应用场景

给定多个区间，如果区间之间有交集那么就结合到一起

给定 nn 个区间 [li,ri]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3] 和 [2,6] 可以合并为一个区间[1,6]。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 l 和 r。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围

1≤n≤100000
?10⁹≤li≤ri≤10⁹

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

代码

#include<bits/stdc++.h> //万能头文件
using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
vector<PII> segs;

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 (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() {

    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;
}

区间合并

原文：https://www.cnblogs.com/mrmrwjk/p/14772544.html