活动选择

题目描述

学校有 $n$ （ $n \le 1000$ ）个活动都想用同一间礼堂，同一时间只能安排一个。给定每个活动的起始时间 $begin_i$ 和结束时间 $end_i$ （ $begin_i < end_i \le 32767$ ），挑出尽可能多的活动使它们两两不冲突，输出这个最大数量。

样例输入：

text

111 3 5 1 4 12 14 8 12 0 6 8 11 6 10 5 7 3 8 5 9 2 13

样例输出：4。

思路

经典区间调度：把所有活动按结束时间升序排序后扫描，维护已选活动的最大结束时刻 last_end，凡是 begin_i >= last_end 的就贪心选上，最终统计的总数就是最大可相容活动数。

参考代码

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#!/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-07-05 21:47
# update_at: 2026-07-05 21:47

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    acts = sorted(
        ((next(data), next(data)) for _ in range(n)),
        key=lambda x: x[1],  # 按结束时间升序，为每次选最早结束者做准备
    )

    ans = 0
    last_end = -1  # 礼堂上次被占用的结束时刻；begin_i 非负，-1 表示尚未使用
    for begin, end in acts:
        can_use = begin >= last_end  # 当前活动与已安排的不冲突
        if can_use:
            ans += 1
            last_end = end

    print(ans)


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/**
 * 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:42
 * update_at: 2026-10-05 09:42
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1005;

ll n;
ll b[MAXN]; // b[i] 第 i 个活动的起始时间
ll e[MAXN]; // e[i] 第 i 个活动的结束时间
ll order[MAXN]; // order[i] 第 i 小的活动下标（按 end 升序）

// 比较函数：先按结束时间升序，结束时间相同时按起始时间升序。
bool cmp_by_end(ll x, ll y) {
    if (e[x] != e[y]) return e[x] < e[y];
    return b[x] < b[y];
}

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

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> b[i] >> e[i];
        order[i] = i;
    }

    // 按结束时间升序排序：每次优先选结束最早的活动，留出更大后续时间窗。
    sort(order + 1, order + n + 1, cmp_by_end);

    ll ans = 0;
    ll last_end = -1; // 已选活动中最后一个的结束时刻；begin_i >= 0，-1 表示尚未选
    for (ll k = 1; k <= n; k++) {
        ll i = order[k];
        if (b[i] >= last_end) { // 与已选集合不相交，可选
            ans++;
            last_end = e[i];
        }
    }

    cout << ans << "\n";
    return 0;
}

目录

题目描述

思路

参考代码