最大不相交区间数量：优先选择最早结束的

1 问题：一天最多参加几场比赛

给定若干活动的开始时间和结束时间，参加一个活动必须从头到尾，不能同时参加两个活动。怎样安排，才能参加最多的活动？

把每个活动画成时间轴上的一个区间，就是最大不相交区间数量问题，也叫区间调度或活动选择问题。

这里的「最大」指的是选出的区间个数最多，不是总长度最长。

2 例题：洛谷 P1803

题目：luogu P1803: 凌乱的yyy / 线段覆盖。

有 $n$ 场比赛，第 $i$ 场从 $a_i$ 开始，到 $b_i$ 结束，满足 $a_i<b_i$。每场比赛必须完整参加，不能同时参加两场比赛，求最多能参加几场。

输入格式：第一行是 $n$，随后 $n$ 行，每行两个整数 $a_i,b_i$。

输出格式：一个整数，表示最多能参加的比赛数。

数据范围：$1\le n\le10^6$，$0\le a_i<b_i\le10^6$。

1
2
3
4
5
6
7
8

输入：
3
0 2
2 4
1 3

输出：
2

选择 $[0,2)$ 和 $[2,4)$，可以参加两场。样例也明确告诉我们：结束时间等于下一场的开始时间，不算冲突。

3 先想暴力：每场选或不选

每场比赛都有「参加」与「不参加」两种选择，枚举全部子集，再判断其中的比赛是否冲突，就能找到正确答案。

判断一个子集时，可以按开始时间排列所选比赛，检查相邻两场是否满足「前一场结束不晚于后一场开始」。

这样的做法需要枚举 $2^n$ 个子集，只适合很小的数据。它也提示了问题的难点：每次选一场，都会排除一些与它冲突的比赛。

我们需要找到一种选择：获得同样的一场比赛，却尽量少限制后面的安排。

4 两个看似合理、实际错误的策略

4.1 谁开始得早，就先选谁？

考虑三场比赛：

• $A=[0,10)$；
• $B=[1,2)$；
• $C=[2,3)$。

最早开始的 $A$ 占据了很长时间，只能参加一场；选择 $B,C$ 则能参加两场。

开始得早，不代表结束得早。 我们关心的是选完以后，还能给后面的比赛留多少机会。

4.2 谁持续时间短，就先选谁？

考虑三场比赛：

• $A=[0,4)$；
• $B=[4,8)$；
• $C=[3,5)$。

最短的 $C$ 只有两个时间单位，却同时挡住 $A,B$。选 $C$ 只能参加一场，选 $A,B$ 可以参加两场。

所以「占用时间短」也不是答案。一个区间占据时间轴的什么位置，同样重要。

5 正确选择：能参加的里面，谁结束最早就选谁

假设已经参加完一些比赛，上一个已选比赛的结束时间是 last_end。

下一场必须满足

否则它已经在你空闲之前开始了，无法完整参加。

在所有满足条件的比赛中，优先选择结束时间最早的那一场。原因是：选哪一场都只让答案增加一，但结束得越早，后面可安排的比赛就越多。

这不是「只要有空就随便选一场」：排序保证我们每次碰到的第一场可选比赛，正是结束最早的可选比赛。

6 为什么正确：替换最优方案的第一场

注意我们并没有证明「所有最优方案都必须选择 $g$」。有时有很多种最优安排。贪心只需要保证：选了它之后，仍然能达到最优值。

7 排序后只扫一遍

维护两个量：

• ans：已经选择的比赛数；
• last_end：最后一场已选比赛的结束时间。

扫描时分两种情况：

1. seg[i].l >= last_end：可以完整参加，选择它，更新 last_end = seg[i].r。
2. seg[i].l < last_end：与已选比赛冲突，跳过。

跳过的比赛以后也不必回头考虑：后续 last_end 只会变大，它的开始时间不会再满足条件。

结束时间相同的比赛，先扫描谁都不影响最优数量，因为选中后留下的时间边界相同。代码额外按开始时间升序打破平局，只是为了让排序结果确定。

7.1 样例推演

按结束时间排序后，顺序为 $[0,2),[1,3),[2,4)$。

7.2 完整 C++17 实现

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

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

struct Segment {
    int l;
    int r;
};

int n;
Segment seg[MAXN]; // 每个比赛的开始时间和结束时间

bool cmp_segment(const Segment &a, const Segment &b) {
    if (a.r != b.r) {
        return a.r < b.r;
    }
    return a.l < b.l;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> seg[i].l >> seg[i].r;
    }

    sort(seg + 1, seg + n + 1, cmp_segment);

    int ans = 0;
    int last_end = 0; // 上一个已选比赛的结束时间
    for (int i = 1; i <= n; i++) {
        // 当前比赛开始时间不早于 last_end，就可以接在已选比赛后面。
        if (seg[i].l >= last_end) {
            ans++;
            last_end = seg[i].r;
        }
    }

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

P1803 的开始时间都非负，因此 last_end = 0 可以作为初始值。若迁移到允许负时间的题目，应使用「尚未选择」标记，或按数据范围设置足够小的初始值，不能直接照搬零。

7.3 复杂度

排序需要 $O(n\log n)$ 时间，随后扫描 $O(n)$，总时间复杂度为 $O(n\log n)$。存储全部区间需要 $O(n)$ 空间。

8 四种区间问题，不要混用策略

题目标题不一定准确描述模型。P1803 虽然叫「线段覆盖」，实际求的是最多能选多少个互不冲突的区间，不是用最少区间覆盖目标。

区间选点见 雷达设备，区间分组见 畜栏预定，区间覆盖见 区间覆盖：每次把边界推得最远。

9 自查与练习

• 只有一场比赛：答案是 $1$。
• 多场比赛完全相同：只能选一场。
• 所有比赛首尾相接：可以全部选择，注意使用 >=。
• 一个长区间包含许多短区间：不要被「最早开始」误导。
• 若每场比赛有不同收益，目标改成总收益最大：最早结束优先不再保证最优。例如 $[0,2)$ 收益为 $1$，$[0,3)$ 收益为 $100$，只选前者显然不优，通常需要考虑带权区间调度的动态规划。

完成 luogu P1803: 凌乱的yyy / 线段覆盖 后，可以继续阅读 对拍练习：线段覆盖问题，用暴力、错误贪心和随机数据练习寻找反例。

10 相关题解