难 · 排序+扫描

区间合并

按到来顺序合并区间是灾难 —— 下一个区间可能伸到任何地方。按左端点排序之后，世界变成一条只需走一遍的线，手里只带一个「当前末端」。

一句话答案按左端点冒泡排序，然后扫描：下一个区间的起点不晚于当前末端就把末端延伸成两个右端点的较大者；否则输出已完成的区间、开新的。

题目

输入: 第一行是 n（1 ≤ n ≤ 100）。接下来 n 行，每行两个整数 l 和 r（−1000 ≤ l ≤ r ≤ 1000）：一行一个闭区间，顺序任意。

输出: 合并后的区间，每行一对 l r，按左端点排序。端点相接（前一个的终点等于后一个的起点）也算重叠，必须合并。

样例:

输入	输出
`4 1 3 2 6 8 10 15 18`	`1 6 8 10 15 18`
`2 1 4 4 5`	`1 5`

这里是闭区间：[1,4] 和 [4,5] 共享点 4，所以熔成 [1,5]。如果你的代码写的是 l < end 而不是 l <= end，恰好这类样例会悄悄保持原样输出。

你的解答

main.cpp — 你的解答

「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 排序的是「成对」，不是单个数组

只重排 l[] 会把数据搅乱 —— 每个左端点都拖着自己的右端点。在冒泡排序里意味着：交换 l[j] 和 l[j+1] 时，r[j] 和 r[j+1] 也要跟着换。这台机器你在冒泡排序里已经写过；这里它把两个平行数组当一个整体排。

提示 2 — 一个「当前末端」就是整个扫描

带着 curL, curR（你正在长大的那个区间）走一遍排好序的区间。下一个的起点不晚于 curR 就是重叠：令 curR = max(curR, nextR)（必须取 max，否则被包含的区间会把末端缩回去）。否则当前区间已经完结：打印它，把下一个收作新的当前。

提示 3 — 最后一个区间活在循环之外

扫描只在遇到「不重叠的后继」时才打印当前区间。最后一个没有人跟在后面 —— 所以循环结束后，再打印一次 curL curR。漏掉这行的典型症状：输出永远少一个区间。

题解（先自己试试！）

#include <iostream>
using namespace std;

int l[105], r[105];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> l[i] >> r[i];

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (l[j] > l[j + 1]) {
                int tl = l[j]; l[j] = l[j + 1]; l[j + 1] = tl;
                int tr = r[j]; r[j] = r[j + 1]; r[j + 1] = tr;
            }
        }
    }

    int curL = l[0], curR = r[0];
    for (int i = 1; i < n; i++) {
        if (l[i] <= curR) {
            if (r[i] > curR) curR = r[i];
        } else {
            cout << curL << " " << curR << endl;
            curL = l[i];
            curR = r[i];
        }
    }
    cout << curL << " " << curR << endl;
    return 0;
}

「先排序再扫描」是解决大多数区间/事件问题的六七个模式之一：日程重叠、会议室、信号区段。这里复用的排序来自冒泡排序；等 n 超过一千，你会换成更快的排序，而这趟扫描原封不动 —— 模式和技巧的区别就在这里。

深度解析

为什么这样做对

按左端点排序,把任意的一堆变成一条「重叠只发生在局部」的线:每个区间只可能碰到你手上正在长大的那个。一对跑动变量 (curL, curR) 扫一遍 —— 重叠就延伸(curR = max(curR, r)),有缝就输出重开。先排序,是把搜索问题变成扫描问题的关键一步。

代价

冒泡排序 O(n²),扫描 O(n) —— n ≤ 100 毫无压力。换成真排序后整体 O(n log n);扫描本身永远不涨。

常见错法

只排 l[] 不带着 r[] —— 右端点全体留守,第一次合并之后全盘皆错。平行数组必须一起换。
把 l < curR 写成不等号漏了等号:闭区间端点相接([1,4] 和 [4,5])必须熔合,决定成败的恰恰是这个等号。
循环结束后忘了最后一句 cout << curL << " " << curR —— 扫描只在遇到缝隙时输出,最后一个区间后面没有缝隙。

下一步

复用的排序来自冒泡排序。同一副「先排序再扫描」的骨架跑会议室、日程重叠这些问题 —— 变的只是合并条件。

记住这两句

按左端点排序,然后带一个「当前末端」扫一遍 —— 全部思想。
平行数组一起交换;最后一个区间在循环外打印。

🐞 这段是错的 —— 点开,亲手让它挂一次

只排了左端点,右端点全体留守 —— 配对全乱了

#include <iostream>
using namespace std;

int l[105], r[105];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> l[i] >> r[i];
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (l[j] > l[j + 1]) {
                int t = l[j]; l[j] = l[j + 1]; l[j + 1] = t;
                // bug: r[] never swaps — pairs are broken
            }
        }
    }
    int curL = l[0], curR = r[0];
    for (int i = 1; i < n; i++) {
        if (l[i] <= curR) { if (r[i] > curR) curR = r[i]; }
        else { cout << curL << " " << curR << endl; curL = l[i]; curR = r[i]; }
    }
    cout << curL << " " << curR << endl;
    return 0;
}