【例75.2】 区间合并

解题思路

按左端点排序，维护已合并右边界r。下一段左端≤r即可合并并取更大右端，否则出现无法被后续补齐的空隙，输出no。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

闭区间端点相接可合并；[1,2]与[3,4]不可合并，不能用r+1。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (auto &p : a)
        cin >> p.first >> p.second;
    sort(a.begin(), a.end());
    int l = a[0].first, r = a[0].second;
    for (int i = 1; i < n; i++) {
        if (a[i].first > r) {
            cout << "no\n";
            return 0;
        }
        r = max(r, a[i].second);
    }
    cout << l << " " << r << "\n";
    return 0;
}