今年暑假不AC

题目解析

求最多不相交区间的数量

这是一个非常经典的算法题目，属于贪心算法（Greedy Algorithm）中的区间调度问题（Interval Scheduling Problem）。

这道题的核心在于：如何在有限的时间内，尽可能多地安排互不冲突的活动。

以下是对这道题目的详细解析、解题思路以及参考代码。

1. 题目核心分析

目标：选择尽可能多的节目（区间）。
约束：节目之间不能重叠（即上一个节目的结束时间 $\le$ 下一个节目的开始时间）。
输入： $n$ 个节目，每个都有开始时间 $T_s$ 和结束时间 $T_e$ 。

2. 为什么是“贪心”？

我们需要制定一个简单的规则（贪心策略），每次都做出当前看起来最好的选择，从而达到全局最优。对于这道题，我们有几种直觉上的策略，但只有一种是正确的：

策略一（错误）：优先选开始时间最早的。
- 反例：如果有一个节目从 0:00 播到 24:00，选了它就不能看其他任何节目了，但这显然不是最优解。
策略二（错误）：优先选持续时间最短的。
- 反例：节目A [1, 5], 节目B [4, 7], 节目C [6, 10]。B最短（3小时），选了B就不能选A和C（结果为1）。但实际上选A和C能看2个节目。
策略三（正确）：优先选结束时间最早的。
- 原理：结束得越早，留给后面节目的时间资源就越多。 只要这个节目能看（和前一个不冲突），我们就选结束时间最早的那个，这样能最大程度地保留后续空间。

3. 解题步骤

基于“策略三”，我们的算法流程如下：

存储：将所有节目保存下来，每个节目包含 start 和 end 两个属性。
排序：按照结束时间 ( $T_e$ ) 从小到大对所有节目进行排序。如果结束时间相同，开始时间早晚无所谓（或者按开始时间降序也可以，不影响计数）。
选择：
- 初始化计数器 count = 1（默认选第一个排序后的节目）。
- 记录变量 last_end 为第一个节目的结束时间。
- 从第 2 个节目开始遍历：
  - 如果当前节目的 开始时间 ( $T_s$ ) $\ge$ last_end：说明这个节目可以完整看完。
  - 执行操作：count++，并将 last_end 更新为当前节目的结束时间。
  - 否则：跳过该节目（因为它和上一个选中的节目冲突了）。
输出：打印 count。

4. 复杂度分析

时间复杂度：主要消耗在排序上。对于 $n$ 个节目，使用 std::sort 的复杂度是 $O(N \log N)$ 。遍历过程是 $O(N)$ 。所以总时间复杂度是 $O(N \log N)$ 。
空间复杂度：需要存储 $n$ 个节目，复杂度为 $O(N)$ 。

6. 示例演示

假设输入是 Sample 中的前几个数据（手动演示逻辑）：

数据：1 3, 3 4, 0 7, 3 8

排序（按结束时间）：
- 1 3 (结束 3)
- 3 4 (结束 4)
- 0 7 (结束 7)
- 3 8 (结束 8)
遍历：
- 选第1个 1 3：count = 1, last_end = 3。
- 看第2个 3 4：开始时间 3 $\ge$ last_end 3。符合条件！
  - 选它：count = 2, last_end = 4。
- 看第3个 0 7：开始时间 0 < last_end 4。冲突，跳过。
- 看第4个 3 8：开始时间 3 < last_end 4。冲突，跳过。
结果：2。

代码

cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// 定义结构体存储节目的开始和结束时间
struct Show {
    int start;
    int end;
};

// 比较函数：按结束时间从小到大排序
// 如果结束时间相同，怎么排都可以，这里默认按结束时间升序
bool compareShows(const Show &a, const Show &b) {
    return a.end < b.end;
}

int main() {
    int n;
    // 循环处理每个测试实例，直到 n=0
    while (cin >> n && n != 0) {
        vector<Show> shows(n);
        for (int i = 0; i < n; i++) {
            cin >> shows[i].start >> shows[i].end;
        }

        // 1. 贪心策略的核心：按结束时间排序
        sort(shows.begin(), shows.end(), compareShows);

        // 2. 选择第一个结束最早的节目
        int count = 1;
        int last_end = shows[0].end;

        // 3. 遍历剩下的节目
        for (int i = 1; i < n; i++) {
            // 如果当前节目的开始时间 >= 上一个节目的结束时间
            if (shows[i].start >= last_end) {
                count++;
                last_end = shows[i].end; // 更新结束时间
            }
        }

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

目录