区间调度与优化

前言

上一篇 贪心策略与交换论证 介绍了交换论证的基本方法。这篇聚焦贪心最经典的应用领域——区间问题。

区间问题在日常生活中随处可见：一天有 $N$ 场电影（各有开始和结束时间），最多能看几场？$N$ 个任务各有时间窗口，同时进行的任务不能共用资源，最少需要几份资源？这些问题有一个共同的贪心范式：按某个端点排序，然后按某种规则选取。

问题的本质

最多不相交区间（活动选择）

给定 $N$ 个区间 $[L_i, R_i)$，选尽可能多的区间使得它们互不相交。

贪心策略：按右端点排序，能选就选。

为什么按右端点而不是左端点？ 按左端点排序可能选到一个很早开始但很晚结束的区间，霸占大量时间。按右端点排序则保证每次选的区间结束得最早，给后面留出最多空间。

交换论证：假设最优解的第一个区间不是右端点最小的。设贪心选了区间 $A$（右端点最小），最优解选了区间 $B$（右端点更大）。因为 $R_A \le R_B$，把 $B$ 换成 $A$ 不会和后面的区间冲突（$A$ 结束更早，只会更好）。所以存在一个最优解第一步和贪心一样。对剩余子问题递归，贪心就是最优的。

最少点覆盖

用最少的点，使得每个区间至少包含一个点。

策略：按右端点排序，在第一个未覆盖区间的右端点放一个点，跳过所有包含该点的区间。代码和活动选择几乎一样。

区间分组（最少会议室）

$N$ 个会议区间，同时进行的不能共用会议室。最少需要几个？

策略：扫描线。把所有 $L_i$（+1 事件）和 $R_i$（-1 事件）排序，扫描过程中计数器的峰值就是答案。

理论 + 代码

活动选择的标准实现

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

pair<int, int> seg[300009]; // (R_i, L_i) — 右端点在前便于排序

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        int L, R; scanf("%d%d", &L, &R);
        seg[i] = {R, L};                             // ① 存为 (右端点, 左端点)
    }
    sort(seg, seg + N);                              // ② 按右端点排序

    int cnt = 0, lastEnd = -1;                       // ③ lastEnd = 上一个选中区间的右端点
    for (int i = 0; i < N; i++) {
        if (seg[i].second >= lastEnd) {              // ④ 不重叠（允许首尾相接）
            cnt++;
            lastEnd = seg[i].first;                  // ⑤ 更新右端点
        }
    }
    printf("%d\n", cnt);
}

逐行解析：

• ① 存为 (R, L) 而非 (L, R)，这样 sort 自动按 first（右端点）排序。
• ② 按右端点升序排列。
• ③ lastEnd = -1 表示还没有选中任何区间。
• ④ 用 >= 而非 >，允许一个区间在 $R_i$ 结束的瞬间另一个区间在 $R_i$ 开始。
• ⑤ 选中后更新 lastEnd 为当前区间的右端点。

扫描线求峰值

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

pair<int, int> events[600009]; // (时间, +1/-1)

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        int L, R; scanf("%d%d", &L, &R);
        events[2*i] = {L, 1};                        // 开始事件
        events[2*i+1] = {R, -1};                     // 结束事件
    }
    sort(events, events + 2*N);

    int cur = 0, ans = 0;
    for (int i = 0; i < 2*N; i++) {
        cur += events[i].second;
        ans = max(ans, cur);                         // 峰值 = 最少会议室
    }
    printf("%d\n", ans);
}

逐行解析：

• 把每个区间拆成两个事件：开始（+1）和结束（-1）。
• 排序后扫描。同一时刻 second = -1（结束）排在 second = 1（开始）前面，因为 $-1 < 1$。这保证了一个会议结束的瞬间另一个可以立刻开始。

例题

例题 1：M&A 082 — Interval Scheduling Problem（活动选择模板）

题目：$N$ 场电影，第 $i$ 场在 $[L_i, R_i)$ 期间放映。最多能完整看几场？一场结束的瞬间可以开始下一场。

数据范围：$1 \le N \le 3 \times 10^5$，$0 \le L_i < R_i \le 86400$

—— AtCoder M&A 082

分析：标准活动选择。按右端点排序，贪心选取。

输入样例：

3
123 86399
1 86400
86399 86400

输出：2

代码：

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

pair<int, int> seg[300009];

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        int L, R; scanf("%d%d", &L, &R);
        seg[i] = {R, L};
    }
    sort(seg, seg + N);

    int cnt = 0, lastEnd = -1;
    for (int i = 0; i < N; i++) {
        if (seg[i].second >= lastEnd) {              // ① ≥ 允许首尾相接
            cnt++;
            lastEnd = seg[i].first;
        }
    }
    printf("%d\n", cnt);
}

逐行解析：

• ① seg[i].second >= lastEnd：当前电影的开始时间 ≥ 上一场结束时间，不冲突。

验证：3 场 $(123,86399), (1,86400), (86399,86400)$。排序后 $(86399,123), (86400,1), (86400,86399)$。

• 选第 1 场（$R=86399$），lastEnd=86399
• 第 2 场 $L=1 < 86399$，跳过
• 第 3 场 $L=86399 \ge 86399$，选。共 2 场。✓

---

例题 2：TB A39 — Interval Scheduling Problem（同 M&A 082）

题目：同上。

—— AtCoder Tessoku Book A39

说明：Tessoku Book A 系列和 M&A 共享同一题。代码与例题 1 完全相同。

---

例题 3：区间分组——最少会议室

场景：$N$ 个会议区间 $[L_i, R_i)$，同时进行的不能共用会议室。最少需要几个会议室？

数据范围：$1 \le N \le 3 \times 10^5$

分析：扫描线法。把所有时间点排序，遇到开始 +1，遇到结束 -1，峰值即答案。

代码：

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

pair<int, int> events[600009];

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        int L, R; scanf("%d%d", &L, &R);
        events[2*i] = {L, 1};                        // ① 开始事件
        events[2*i+1] = {R, -1};                     // ② 结束事件
    }
    sort(events, events + 2*N);                      // ③ 按时间排序

    int cur = 0, ans = 0;
    for (int i = 0; i < 2*N; i++) {
        cur += events[i].second;                     // ④ 计数器加减
        ans = max(ans, cur);                         // ⑤ 记录峰值
    }
    printf("%d\n", ans);
}

逐行解析：

• ①② 每个区间拆成两个事件：开始（+1）和结束（-1）。
• ③ 同一时刻结束（-1）排在开始（+1）前面，因为 pair 先比 first，first 相同时比 second，而 $-1 < 1$。
• ④⑤ 扫描过程中，cur 是当前同时进行的会议数。峰值就是最少需要的会议室数。

验证：3 个会议 $(1,4), (2,5), (3,6)$。事件：$(1,+1),(2,+1),(3,+1),(4,-1),(5,-1),(6,-1)$。

时间	事件	cur
1	+1	1
2	+1	2
3	+1	3
4	-1	2
5	-1	1
6	-1	0

峰值 = 3，最少需要 3 个会议室。✓（三个会议在时刻 3 同时进行）

---

例题 4：最少点覆盖

场景：$N$ 个区间 $[L_i, R_i]$。用最少的点使每个区间至少包含一个点。

数据范围：$1 \le N \le 3 \times 10^5$

分析：按右端点排序。在第一个未覆盖区间的右端点放一个点，跳过所有包含该点的区间。

代码：

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

pair<int, int> seg[300009]; // (R, L)

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        int L, R; scanf("%d%d", &L, &R);
        seg[i] = {R, L};
    }
    sort(seg, seg + N);

    int cnt = 0, point = -2e9;                       // ① point = 上一个放置的点
    for (int i = 0; i < N; i++) {
        if (seg[i].second > point) {                 // ② 当前区间未被覆盖
            cnt++;
            point = seg[i].first;                    // ③ 在右端点放一个点
        }
    }
    printf("%d\n", cnt);
}

逐行解析：

• ① point = -2e9 确保第一个区间一定会被处理。
• ② 如果区间的左端点 > 已放置的点，说明该区间没被覆盖。
• ③ 在右端点放点是最优的——放在右端点可以覆盖最多后续区间（因为后续区间的左端点只会更大）。

验证：4 个区间 $(1,3), (2,5), (4,7), (6,8)$。排序后同。

• 区间 1 未覆盖，在 3 放点。覆盖 $(1,3), (2,5)$。
• 区间 3：$L=4 > 3$，未覆盖。在 7 放点。覆盖 $(4,7), (6,8)$。
• 共 2 个点。✓

---

例题 5：带权活动选择——区间 DP

场景：$N$ 个区间 $[L_i, R_i)$，每个有权值 $W_i$。选若干不相交区间使权值和最大。

数据范围：$1 \le N \le 2 \times 10^5$

分析：无权版用贪心，但带权版需要 DP。按右端点排序后，$dp[i]$ = 考虑前 $i$ 个区间时的最大权值和。$dp[i] = \max(dp[i-1],\ dp[j] + W_i)$，其中 $j$ 是最后一个满足 $R_j \le L_i$ 的区间。用二分搜索找 $j$。

代码：

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

pair<int, int> seg[200009]; // (R, L)
long long W[200009];
long long dp[200009];

int main() {
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        int L, R; long long w;
        scanf("%d%d%lld", &L, &R, &w);
        seg[i] = {R, L};
        W[i] = w;
    }
    sort(seg + 1, seg + N + 1);                      // ① 按右端点排序

    int sortedR[200009];
    for (int i = 1; i <= N; i++) sortedR[i] = seg[i].first;

    dp[0] = 0;
    for (int i = 1; i <= N; i++) {
        // ② 二分找最后一个 R_j <= L_i 的 j
        int j = lower_bound(sortedR + 1, sortedR + i, seg[i].second) - sortedR - 1;
        dp[i] = max(dp[i-1], dp[j] + W[i]);          // ③ 不选 or 选
    }
    printf("%lld\n", dp[N]);
}

逐行解析：

• ① 按右端点排序，保证处理第 $i$ 个区间时前面所有的右端点都不超过 $R_i$。
• ② lower_bound 找第一个 $\ge L_i$ 的右端点位置，减 1 得到最后一个 $\le L_i$ 的。这保证了区间 $j$ 和区间 $i$ 不重叠。
• ③ 不选第 $i$ 个区间：$dp[i-1]$。选第 $i$ 个：找不冲突的最后一个区间 $j$，$dp[j] + W_i$。

参考文献

基础练习 — アルゴリズムと数学 演習問題集

• 082 Interval Scheduling Problem（活动选择模板）【例题】

系统练习 — 競技プログラミングの鉄則

• A39 Interval Scheduling Problem（同 M&A 082）【例题】

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化