基础算法：区间合并-526互联

1、区间合并

以AcWing.803为例，题目要求如下：

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

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

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

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

输入格式
第一行包含整数 n。

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

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

数据范围
1≤n≤100000,−10^9≤li≤ri≤10^9

输入样例：
5
1 2
2 4
5 6
7 8
7 9

输出样例：
3

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using PII = pair<int, int>;

const int N = 1e6 + 10;

vector<PII> segs;

void merge(vector<PII>& segs, vector<PII>& res) {
    int start = -2e9, end = -2e9;
    for (auto seg : segs) {
        if (seg.first > end) {
            if (start != -2e9) res.push_back({ start, end });
            start = seg.first, end = seg.second;
        }
        else {
            end = max(end, seg.second);
        }
    }

    if (start != -2e9) res.push_back({ start, end });
    
    return;
}

int main() {
    int n;
    cin >> n;

    int l, r;
    while (n--) {
        cin >> l >> r;
        segs.push_back(make_pair(l, r));    
    }

    sort(segs.begin(), segs.end());
    
    vector<PII> res;
    merge(segs, res);

    cout << res.size() << endl;
    
    return 0;
}