P4796 区间合并（基础）

解题思路

1. 读懂题目：给定 n 个闭区间，任意两个相邻或相交的区间可以合并成一个。问这 n 个区间最终能不能全部合并成一个大区间。能，就输出合并后区间的左右端点；不能，就输出 no。

2. 什么样的两个区间能合并：如果两个闭区间有公共部分，或者一个的右端等于另一个的左端（紧挨着），就能合并。比如 [1,2] 和 [2,3] 能合并成 [1,3]，[1,2] 和 [3,4] 中间隔着空当，就不能合并。

3. 贪心策略：先把所有区间按"左端点从小到大"排序，左端点相同就按右端点从小到大排。然后从第一个区间开始，用一个"当前合并区间"记录已经合并出来的范围 [curLeft, curRight]。

4. 逐个扫描判断：对排好序的每个新区间，如果它的左端 ≤ curRight，说明它和当前合并区间相交或相邻，可以并进来，把 curRight 更新成两者右端的较大值；如果它的左端 > curRight，说明中间出现了断档（空白），就不可能全部合并成一个区间了，直接输出 no。

5. 为什么排序后这样扫就够：按左端点排序后，后面的区间左端只会越来越大。如果当前区间接不上（左端比 curRight 还大），后面的区间左端更大，更不可能接上，所以可以立刻停止。

6. 看例子：样例区间排序后是 (1,5),(5,6),(6,9),(8,10),(10,10)。合并过程：1-5 → 并 5-6 得 1-6 → 并 6-9 得 1-9 → 并 8-10 得 1-10 → 并 10-10 仍为 1-10。输出 1 10。

7. 边界情况：像 (10,10) 这样只有一个点的区间也能参与合并；如果第一个区间和第二个区间就断开，直接输出 no。

8. 数据规模提醒：n 最大到 50000，如果用两层循环的冒泡排序会非常慢甚至超时，所以参考代码里用了 自带的 sort 函数，它是 O(n log n) 的快排。

参考代码

// P4796 区间合并：按左端点排序，逐个并入当前区间，出现断档就输出 no
#include <iostream>
#include <algorithm>
using namespace std;
struct Interval { int left; int right; };  // 闭区间的左右端点
Interval arr[50005];

// 比较函数：左端点小的在前，左端点相同则右端点小的在前
bool cmp(const Interval& a, const Interval& b) {
    if (a.left != b.left) return a.left < b.left;
    return a.right < b.right;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i].left >> arr[i].right;
    sort(arr, arr + n, cmp);
    int curLeft = arr[0].left;   // 当前合并区间的左端
    int curRight = arr[0].right; // 当前合并区间的右端
    bool canMerge = true;        // 是否所有区间都能合并成一个
    for (int i = 1; i < n; i++) {
        if (arr[i].left <= curRight) {
            // 与当前区间相交或相邻，合并后右端取更大的
            if (arr[i].right > curRight) curRight = arr[i].right;
        } else {
            // 出现了断档，无法全部合并
            canMerge = false;
            break;
        }
    }
    if (canMerge) cout << curLeft << " " << curRight << endl;
    else cout << "no" << endl;
    return 0;
}

复杂度分析

排序用 sort 函数，时间复杂度 O(n log n)；排序后只需要扫一遍区间，是 O(n)。n 最大 50000，O(n log n) 大概几十万次运算，轻松通过。空间上用了长度 50005 的结构体数组，是 O(n)。