「一本通 1.1 练习 3」线段

题目描述

数轴上有 $n$ 条线段，第 $i$ 条由整数端点 $a_i, b_i$ 表示。要求选出尽量大的子集，使得任意两条线段没有重合部分（端点相接不算重合），输出最大条数。输入第一行为 $n$ ，接下来 $n$ 行每行两个整数 $a_i, b_i$ 。样例输入 3 / 0 2 / 2 4 / 1 3，输出 2。

思路

把所有线段按右端点从小到大排序；维护已选最后一条线段的右端点 last_right，若当前线段左端点 $\geqslant$ last_right 就选中并更新，否则跳过。

参考代码

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

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    segments = sorted(((next(data), next(data)) for _ in range(n)), key=lambda s: s[1])  # 按右端点从小到大排序

    # 贪心：每次选右端点最小且与已选不重叠的线段
    count = 0
    last_right = None  # 已选最后一条线段的右端点
    for left, right in segments:
        not_overlap = last_right is None or left >= last_right  # 端点相接不算重合
        if not_overlap:
            count += 1
            last_right = right

    print(count)


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/**
 * 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 23:31
 * update_at: 2026-10-05 23:31
 */
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 1000005; // 最大线段数

struct Seg {
    ll l, r;
} seg[MAXN];

// 按右端点升序排序
bool cmp(Seg a, Seg b) {
    return a.r < b.r;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld %lld", &seg[i].l, &seg[i].r);
    }
    sort(seg + 1, seg + n + 1, cmp);
    int ans = 0;
    ll last_right = -1; // 已选最后一条线段的右端点
    for (int i = 1; i <= n; i++) {
        if (last_right == -1 || seg[i].l >= last_right) {
            ans++;
            last_right = seg[i].r;
        }
    }
    printf("%d\n", ans);
    return 0;
}

「一本通 1.1 练习 3」线段

目录

题目描述

思路

参考代码