活动安排

题目描述

有 $n$ 个活动要独占同一资源，活动 $i$ 占用时间区间 $[s_i, f_i)$ ，两个活动区间不重叠即可同时安排，求最多能安排的活动数。输入第一行 $n\ (n \le 1000)$ ，接下来 $n$ 行每行两个整数 $s_i, f_i$ ；输出最多互相兼容的活动个数。

样例输入： $n=4$ ，活动为 $(1,3),(4,6),(2,5),(1,7)$ ；样例输出：2。

思路

按结束时间升序排序后依次扫描，若当前活动的开始时间不早于已选活动的结束时间，就选它并更新结束时间；结束越早留给后续的空间越大，因此该贪心最优。

参考代码

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

import sys


def max_compatible_activities(intervals: list[tuple[int, int]]) -> int:
    """按结束时间贪心选取尽可能多的互不重叠活动。"""
    count = 0
    last_end = -1
    for start, end in sorted(intervals, key=lambda x: x[1]):
        if start >= last_end:
            count += 1
            last_end = end
    return count


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        n = next(data)
    except StopIteration:
        return
    intervals = [(next(data), next(data)) for _ in range(n)]
    print(max_compatible_activities(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/**
 * 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:14
 * update_at: 2026-10-05 23:14
 */
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 1005; // 活动数不超过 1000

struct Activity {
    ll start;
    ll end;
};

Activity act[MAXN]; // act[i] 表示第 i 个活动的起止时间

// 按结束时间升序排序的比较函数
bool cmp_end(const Activity &a, const Activity &b) {
    return a.end < b.end;
}

int main() {
    ll n;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> act[i].start >> act[i].end;
    }

    // 贪心：按结束时间升序排序后，尽量选择结束早且不冲突的活动
    sort(act + 1, act + n + 1, cmp_end);

    ll count = 0;
    ll last_end = -1; // 上一个已选活动的结束时间
    for (ll i = 1; i <= n; i++) {
        if (act[i].start >= last_end) {
            count++;
            last_end = act[i].end;
        }
    }

    cout << count << endl;
    return 0;
}

目录

题目描述

思路

参考代码