区间调度

前言：贪心——做出局部最好的选择

你有一个会议室，一天里有 $n$ 个会议要开，每个会议有固定的开始和结束时间。一个会议室同一时间只能开一个会。问：最多能安排多少个会议？

直觉上，“选结束时间最早的会议”似乎能让后面的选择更多。但直觉不一定对——为什么不是选最短的会议？或者开始最早的？

贪心算法的难点就在这里：局部最优的选择不一定导致全局最优。你必须证明”每一步贪心都安全”。

区间调度是最经典的贪心问题之一，也是学习贪心证明方法的最佳起点。它的证明非常优雅：假设最优解的第一个会议结束得更晚，把它换成结束更早的，不影响后续选择，所以不会更差。

这篇笔记会讲清楚贪心策略、为什么它是对的、怎么实现，最后通过一道活动安排的例题巩固。

区间调度

问题的本质

给定 $n$ 个区间 $[l_i, r_i]$，选出尽量多的互不重叠的区间。

朴素：枚举所有子集，$2^n$。不行。

关键洞察：直觉上，“早结束的区间”给后面留的空间更多。贪心地每次选结束最早的、能与已选区间兼容的区间，不会比最优解差。

贪心策略：按右端点排序

1. 所有区间按 $r_i$ 从小到大排序
2. 从左往右扫，能选就选（起点 ≥ 上一个选中的终点）

为什么最优？反证法：假设最优解的第一个区间结束于 $r^*$，而贪心选了结束于 $r_1$。因为按右端点排序，$r_1 \le r^*$。把最优解的第一个区间换成贪心的第一个区间，不减少可用的后续空间，剩余部分仍能取到最优。

实现

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

pair<int, int> iv[100006];  // (右端点, 左端点)

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &iv[i].second, &iv[i].first);

    sort(iv, iv + n);  // 按 first（右端点）排序

    int cnt = 0, last_end = -1e9;
    for (int i = 0; i < n; i++) {
        if (iv[i].second >= last_end) {  // 起点 ≥ 上一终点
            cnt++;
            last_end = iv[i].first;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

存成 pair<右端点, 左端点> 可以直接 sort，因为 pair 默认按 first 排序。

复杂度

排序 $O(n \log n)$，扫描 $O(n)$，总计 $O(n \log n)$。

常见区间贪心变体

问题	策略	排序方式
最多不重叠区间	选结束最早的	按右端点排序
最少点覆盖所有区间	选出现最晚的必须位置	按右端点排序，贪心放点
最大不相交区间集	同”最多不重叠”	按右端点排序

核心都一样：让当前选择给未来留下最大的空间。

例题：活动安排

有 $n$ 个活动，每个活动有开始和结束时间。一个场地同一时间只能进行一个活动，问最多能安排多少个活动。

$1 \le n \le 10^5$

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

pair<int, int> a[100006];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &a[i].second, &a[i].first);

    sort(a, a + n);

    int cnt = 0, end = -1e9;
    for (int i = 0; i < n; i++) {
        if (a[i].second >= end) {
            cnt++;
            end = a[i].first;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

解析：标准区间调度。按结束时间排序后贪心选取——每个活动结束时越早，后面能接的活动就越多。pair 巧用 first 存右端点，省去自定义比较器。边界情况注意：活动 $A$ 结束时间为 $t$，活动 $B$ 开始时间为 $t$，这里用 >= 允许首尾相接。