区间合并

题目描述

给定 $n$ 个闭区间 $[a_i; b_i]$ （ $3 \le n \le 50000$ ， $1 \le a_i \le b_i \le 10000$ ），任意两个相交或相邻的闭区间可以合并。判断能否最终合并成一个闭区间：能则输出该区间的左右端点，否则输出 no。

输入第一行 $n$ ，之后 $n$ 行每行两个整数 $a_i, b_i$ 。样例输入 5、5 6、1 5、10 10、6 9、8 10，输出 1 10。

思路

按左端点升序排序，只维护已并入区间的最大右端点 reach。逐行比较：若当前左端点大于 reach，中间出现谁都跨不过的断口，立即输出 no，否则 reach 取自身与当前右端点的较大值。全程无断口时并集就是 [最小左端点, reach]；闭区间相邻也算合并，所以断口判定用严格大于 >。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 01:08
# update_at: 2026-09-30 01:11

import sys


def union_span(intervals: list[tuple[int, int]]) -> tuple[int, int] | None:
    """把 n 个区间按左端点升序后单向扫描：返回这 n 个区间的并集闭区间 [left, right]，并集断开则返回 None。

    按左端点升序后只跟踪一个 reach——已并入区间的最大右端点。下一个左端点若越过它，
    中间就出现一段谁也盖不到的空隙，后面的区间左端点只会更大，并集被永久劈开。
    左端点最小者必然排在最左，所以 merged_left 与 reach 的初值取排序后的首行即可。
    """
    ordered = sorted(intervals)
    merged_left, reach = ordered[0]

    for left, right in ordered[1:]:          # 首行已并好，从这里起才不会重复计入自己
        if left > reach:                     # 越过已覆盖范围，中间出现断口
            return None
        reach = max(reach, right)

    return merged_left, reach


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)                           # 题面的 n，3 <= n <= 50000
    intervals = [(next(data), next(data)) for _ in range(n)]

    ans = union_span(intervals)
    print(f"{ans[0]} {ans[1]}" if ans else "no")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 06:12
 * update_at: 2026-10-05 06:12
 */
// main.cpp：按左端点排序后单遍扫描，判断区间并集是否为一个闭区间。
#include <algorithm>
#include <iostream>
using namespace std;

const int MAXN = 50005;

typedef long long ll;

struct Interval {
    ll left;
    ll right;
};

ll n;
Interval a[MAXN]; // a[i] 表示第 i 个闭区间 [left, right]

// 按左端点升序排序，保证扫描时左端点单调不减。
bool cmp_interval(const Interval &x, const Interval &y) {
    return x.left < y.left;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i].left >> a[i].right;
    }

    sort(a + 1, a + n + 1, cmp_interval);

    ll merged_left = a[1].left; // 最小左端点就是并集的左端点
    ll reach = a[1].right;      // 已并入区间的最大右端点

    for (ll i = 2; i <= n; i++) {
        if (a[i].left > reach) {
            // 左端点越过 reach，中间出现谁都盖不到的空隙，并集被永久劈开。
            cout << "no" << '\n';
            return 0;
        }
        if (a[i].right > reach) {
            reach = a[i].right;
        }
    }

    cout << merged_left << ' ' << reach << '\n';
    return 0;
}

目录

题目描述

思路

参考代码