题意概括

给定一个由多个区间 [start, end] 组成的集合。你的任务是合并所有相互重叠的区间，最终返回一个不包含任何重叠的、能够覆盖所有输入区间的区间集合。

输出要求:

• 合并后的区间集合必须覆盖所有输入区间。
• 集合内的区间之间不能有重叠。
• 输出的区间需要按照它们的起始点进行升序排列。

数据范围:

• 区间的数量 n 满足 $1 \le n \le 10^4$。
• 对于每个区间 [start, end]，保证 start <= end。

基础知识

这是一个经典的区间问题，最有效和标准的解法是采用 排序 + 线性扫描 (Sort + Linear Scan) 的策略。

核心思想:

问题的关键在于，如果我们能以一种有序的方式来处理这些区间，合并操作就会变得非常简单。具体来说，我们可以将所有区间按其起始点 start 进行升序排序。排序之后，能够与当前区间 intervals[i] 发生重叠的，只可能是那些在它之前且结束点 end 尽量大的区间。

算法流程:

1. 排序: 将所有输入的区间按照它们的起始点 start 从小到大进行排序。这是整个算法最关键的一步。
2. 初始化结果集: 创建一个用于存放最终结果的列表 res。首先将排序后的第一个区间直接放入 res 中。
3. 遍历与合并: 从排序后的第二个区间开始，向后遍历每一个区间 cur。我们将 cur 与结果集 res 中最后一个区间 last 进行比较：
   • 情况一：重叠 (Merge) 如果 cur 的起始点 cur.start 小于或等于 last 的结束点 last.end，即 cur.start <= last.end，这说明 cur 和 last 存在重叠部分。我们需要将它们合并。合并操作很简单：我们只需要更新 last 的结束点，使其变为 last.end 和 cur.end 中的较大值。即 last.end = max(last.end, cur.end)。
   • 情况二：不重叠 (Append) 如果 cur 的起始点 cur.start 大于 last 的结束点 last.end，说明这两个区间是完全分离的，无法合并。此时，我们将 cur 作为一个新的、独立的区间，直接添加到结果集 res 的末尾。
4. 返回结果: 当遍历完所有区间后，res 中存储的就是最终合并完成的、无重叠的区间集合。由于我们的输入是排序过的，并且是按顺序处理的，所以 res 中的区间也自然是按起始点排好序的。

复杂度分析:

• 时间复杂度: 算法的主要开销在于第一步的排序，因此总时间复杂度为 $O(N \log N)$，其中 $N$ 是区间的数量。后续的线性扫描合并过程仅需 $O(N)$。
• 空间复杂度: 我们需要一个额外的数据结构来存储合并后的结果。在最坏情况下（即所有区间都不重叠），需要存储全部 N 个区间，因此空间复杂度为 $O(N)$。

C++ 解决方案

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 定义区间结构体，方便操作
struct Seg {
    int l, r;
};

// 自定义排序规则：按左端点升序排序
bool cmp(const Seg& a, const Seg& b) {
    return a.l < b.l;
}

void slv() {
    int n;
    cin >> n;

    vector<Seg> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i].l >> v[i].r;
    }

    if (n == 0) {
        return;
    }

    // 步骤1: 排序
    sort(v.begin(), v.end(), cmp);

    vector<Seg> res;
    // 步骤2: 初始化结果集
    res.push_back(v[0]);

    // 步骤3: 遍历与合并
    for (int i = 1; i < n; ++i) {
        Seg& last = res.back();
        Seg& cur = v[i];

        // 情况一：重叠，更新最后一个区间的右端点
        if (cur.l <= last.r) {
            last.r = max(last.r, cur.r);
        } 
        // 情况二：不重叠，直接将当前区间加入结果集
        else {
            res.push_back(cur);
        }
    }

    // 输出结果
    for (const auto& seg : res) {
        cout << seg.l << " " << seg.r << endl;
    }
}

int main() {
    // 关闭同步流，加速IO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    slv();

    return 0;
}

/*
样例输入 1:
4
1 3
2 6
8 10
15 18

样例输出 1:
1 6
8 10
15 18

样例输入 2:
2
1 4
4 5

样例输出 2:
1 5
*/