📚 P1803 凌乱的yyy / 线段覆盖 超详细讲解

这道题是经典的贪心算法入门题，也叫「活动安排问题」，核心是用贪心策略选出最多不重叠的区间（比赛）。

---

一、题目拆解

问题本质

给定 $n$ 个区间（每个区间代表一个比赛，$[a_i, b_i]$ 是开始-结束时间），要求选出最多数量的互不重叠的区间（不能同时参加两个比赛，必须完整参加），输出最大数量。

输入输出样例分析

输入：

3
0 2
2 4
1 3

3个比赛的时间区间：

• 比赛1：[0, 2]
• 比赛2：[2, 4]
• 比赛3：[1, 3]

最优选择：选比赛1 [0,2] + 比赛2 [2,4]，共2个，和输出一致。 如果选比赛3 [1,3]，就只能再选1个，总数1，不是最优。

---

二、核心思路：贪心算法

为什么用贪心？

这道题的最优解可以通过局部最优推导出全局最优： 每次选择「当前能选的、结束时间最早」的比赛，这样能给剩下的比赛留出最多的时间，从而选出最多的比赛。

完整步骤（对应你截图里的笔记）

1. 输入所有比赛的开始时间 $a_i$ 和结束时间 $b_i$ 把每个比赛存成一个区间 (l, r)，l 是开始，r 是结束。
2. 按结束时间 $r$ 从小到大排序所有区间 这是贪心的核心：永远优先选结束最早的，给后续留最多时间。
3. 贪心遍历选区间
   • 初始化：ans = 0（计数参加的比赛数），last_end = 0（上一个选中比赛的结束时间，初始为0）
   • 遍历排序后的区间：
     • 如果当前区间的开始时间 $l \ge$ 上一个结束时间 last_end（不重叠），就选这个比赛：
       • ans += 1（计数+1）
       • 更新 last_end = 当前区间的结束时间 r
     • 否则跳过（重叠，不能选）
4. 输出最终的 ans，就是最多能参加的比赛数。

---

三、代码逐行解析（C++版，对应你截图的代码）

#include <iostream>
#include <algorithm>
using namespace std;

// 定义比赛的结构体，存开始l和结束r
struct Game {
    int l, r;
} gs[1000005]; // 数组大小开1e6+5，满足n≤1e6的要求

// 排序规则：按结束时间r从小到大排序
bool cmp(Game g1, Game g2) {
    return g1.r < g2.r;
}

int main() {
    int n, ans = 0, mark = 0; // mark = last_end，记录上一个比赛的结束时间
    cin >> n;
    // 输入n个比赛的开始、结束时间
    for(int i = 0; i < n; i++) 
        cin >> gs[i].l >> gs[i].r;
    // 按结束时间排序
    sort(gs, gs + n, cmp);
    // 贪心遍历
    for(int i = 0; i < n; i++) {
        // 如果当前比赛开始时间 >= 上一个结束时间（不重叠）
        if(mark <= gs[i].l) {
            ans++; // 计数+1
            mark = gs[i].r; // 更新结束时间
        }
    }
    cout << ans; // 输出结果
    return 0;
}

代码对应样例的执行过程

排序后的区间（按r从小到大）：

• [0,2]（r=2）、[1,3]（r=3）、[2,4]（r=4）

遍历过程：

1. mark=0，0 <= 0 → 选[0,2]，ans=1，mark=2
2. mark=2，2 <= 1 不成立 → 跳过[1,3]
3. mark=2，2 <= 2 成立 → 选[2,4]，ans=2，mark=4 最终输出2，完全正确。

---

四、Python 实现（适配题目要求，支持pypy3）

import sys

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    games = []
    idx = 1
    for _ in range(n):
        l = int(input[idx])
        r = int(input[idx+1])
        games.append( (r, l) ) # 存成(结束, 开始)，方便排序
        idx += 2
    # 按结束时间排序
    games.sort()
    ans = 0
    last_end = 0
    for r, l in games:
        if l >= last_end:
            ans += 1
            last_end = r
    print(ans)

if __name__ == "__main__":
    main()

注意：Python 用 sys.stdin.read() 一次性读入，避免n=1e6时超时，pypy3 提交更稳。

---

五、关键知识点&避坑指南

1. 为什么按结束时间排序是最优的？

反证法： 假设存在一个最优解，不是按结束时间选的。我们可以把最优解中第一个「不是结束最早」的区间，替换成「结束最早」的区间，得到一个同样不重叠、数量相同的新最优解。 重复这个过程，最终会得到一个「按结束时间选」的最优解，证明贪心策略的正确性。

2. 常见错误思路

• ❌ 按开始时间排序：会选到开始早但结束晚的区间，导致后续能选的变少（比如样例中[0,2]和[1,3]，按开始排序会先选[0,2]，看似没问题，但如果有[0,10]，就会直接占满所有时间，只能选1个，远不如贪心的最优解）
• ❌ 按区间长度排序：同样会出现「短区间但结束晚」的问题，无法保证全局最优
• ❌ 不排序直接遍历：完全随机，结果错误

3. 数据范围注意

题目中 $n \le 10^6$，所以：

• C++ 数组要开够（1e6+5），不能用vector频繁扩容（当然vector也可以，但静态数组更稳）
• Python 必须用快速读入（sys.stdin.read()），否则input()逐行读会超时
• 排序时间复杂度是 $O(n\log n)$，遍历是$O(n)$，总复杂度$O(n\log n)$，完全满足$1e6$数据的要求

---

六、同类问题拓展

这道题是「区间调度」的基础题，同类问题：

1. 区间覆盖问题：用最少的区间覆盖整个线段（贪心策略：按开始时间排序，每次选覆盖当前起点的、结束最远的区间）
2. 区间合并问题：合并所有重叠的区间，输出合并后的区间
3. 区间选点问题：用最少的点，让每个区间都至少包含一个点（贪心策略：按结束时间排序，每次选区间的结束点）

---

七、总结

这道题的核心就是**「结束时间最早」的贪心策略**，记住这个思路，就能秒杀所有同类活动安排问题。 代码逻辑非常简洁，关键是理解「为什么按结束时间排序是最优的」，而不是死记代码。

---

要不要我帮你把这道题的C++和Python代码都优化到极限性能，同时补充一份「区间调度类问题的贪心策略对照表」，方便你以后刷题？