AcWing 803.区间合并

摘要：
一道经典的区间合并问题。

题目

给定 n 个区间 [li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3]和[2,6]可以合并为一个区间[1,6]。

输入格式
第一行包含整数n。
接下来n行，每行包含两个整数 l 和 r。

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

数据范围
1≤n≤100000,
−1e9≤li≤ri≤1e9

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

---

区间合并

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

void merge(vector<PII> &segs) 
{
    vector<PII> res;
    int l = segs[0].first, r = segs[0].second;                  // 2
    for (int i = 1; i < segs.size(); i ++ ) {
        if (r < segs[i].first) {                                // 3
            res.push_back({l, r});
            l = segs[i].first, r = segs[i].second;              // 4
        }                                          
        else r = max(r, segs[i].second);                        // 5
    }
    res.push_back({l, r});                                      // 6
    segs = res;
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<PII> segs;
    for (; n -- ;) {                                         
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    sort(segs.begin(), segs.end());                             // 1  
    merge(segs);
    cout << segs.size() << endl;
    return 0;
}

• 1. 区间按照左端点排序。sort()用于排序pair类时，默认按照左端点升序排序。
• 2. 初始化区间左右端点，后面会更新它们。因为题目指出区间数量n >= 1，所以这里是初始化为排序后的第一个区间。
• 3. 比较两个区间是否相交。
• 4. 不相交情况下更新前置区间左右端点。
• 5. 相交情况下更新前置区间左右端点。（此时只需更新右端点）
• 6. 处理最后一个前置区间，此时前置区间必然是孤立区间。因为n >= 1且最后一个前置区间没有下一个当前区间。

题目链接：
AcWing 803.区间合并