【例6.6】整数区间

题目描述

给定 $n$ 个闭区间 $[a_i, b_i]$ （ $0 \leqslant a_i \leqslant b_i \leqslant 10000$ ），求一个元素个数最少的整数集合 $S$ ，使每个区间内都至少有一个 $S$ 中的整数，输出 $|S|$ 。输入第一行 $n$ （ $1 \leqslant n \leqslant 10000$ ），接下来 $n$ 行每行两个整数 $a,b$ ；输出最少元素个数。样例输入：4 后接 3 6、2 4、0 2、4 7；样例输出：2。

思路

把区间按右端点升序排序。用 last 记录已选点中的最大值（初值 -1 表示还没选点），扫描时若 $a_i > \text{last}$ ，说明该区间没有被任何已选点覆盖，必须新增一个点，且取它的右端点 $b_i$ 能覆盖后面尽量多的区间。这种取法总可以延拓成最优解，因为每次触发新增点所对应的区间两两不相交。

参考代码

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#!/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 05:19
# update_at: 2026-09-30 05:27

import sys

NO_POINT = -1  # 哨兵：表示"还没选过任何点"；所有左端点 a ≥ 0，故它一定小于任何 a


def min_points(intervals: list[tuple[int, int]]) -> int:
    """最少要点数覆盖全部闭区间：按右端点升序扫描，未覆盖的区间就取走它的右端点。"""
    last = NO_POINT  # 已选点中的最大值，即最近一次选中的点
    count = 0
    for a, b in sorted(intervals, key=lambda seg: seg[1]):  # 右端点升序：让"取 b"不会失效
        if a > last:  # 此时所有已选点都 < a，本区间必须新增点；取 b 能覆盖的后续区间最多
            last = b
            count += 1
    return count


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)                                                 # 区间个数
    intervals = [(next(data), next(data)) for _ in range(n)]
    print(min_points(intervals))


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
58
59/**
 * 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 09:41
 * update_at: 2026-10-05 09:41
 */
// main.cpp：区间点覆盖（用最少的点刺穿所有闭区间）的贪心解。
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 10005;

struct Interval {
    ll a; // 左端点
    ll b; // 右端点
};

ll n;
Interval seg[MAXN]; // 所有区间，按右端点升序排序后扫描

// 按右端点升序比较，供 sort 使用。
bool cmp_by_right(const Interval &x, const Interval &y) {
    return x.b < y.b;
}

void read_input() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> seg[i].a >> seg[i].b;
    }
}

void solve() {
    sort(seg + 1, seg + n + 1, cmp_by_right); // 按右端点升序，保证"取右端点"不劣

    ll last = -1; // 已选点中的最大值，-1 表示还没选过点（所有左端点 >= 0）
    ll count = 0;
    for (ll i = 1; i <= n; i++) {
        if (seg[i].a > last) { // 所有已选点都小于左端点，本区间必须新增点
            last = seg[i].b;   // 取右端点能覆盖的后续区间最多
            count++;
        }
    }
    cout << count << '\n';
}

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

    read_input();
    solve();

    return 0;
}

【例6.6】整数区间

目录

题目描述

思路

参考代码