一、活动选择问题（Activity Selection Problem）
问题定义
活动选择问题（Activity Selection Problem）是贪心算法最经典的入门问题之一。给定 n 个活动，每个活动 i 有一个开始时间 s[i] 和结束时间 f[i]，同一时间只能进行一个活动。目标是选择最多数量的互不重叠的活动。
形式化定义：寻找最大子集 S ⊆ {1, 2, ..., n}，使得对于任意 i, j ∈ S（i ≠ j），有 f[i] ≤ s[j] 或 f[j] ≤ s[i]。
1.1 最早结束时间贪心策略
活动选择问题的核心贪心策略是最早结束时间优先（Earliest Finish Time First, EFT）：
- 将所有活动按结束时间 f[i] 从小到大排序
- 选择结束时间最早的活动
- 移除所有与该活动时间冲突的活动
- 重复上述步骤直到所有活动处理完毕
算法伪代码
GreedyActivitySelector(s[], f[], n):
A = {1}
k = 1
for m = 2 to n:
if s[m] ≥ f[k]:
A = A ∪ {m}
k = m
return A
C++ 实现
struct Activity {
int id;
int start;
int finish;
};
bool cmp(Activity a, Activity b) {
return a.finish < b.finish;
}
vector<
int>
greedyActivitySelect(
vector<Activity>& acts) {
sort(acts.begin(), acts.end(), cmp);
vector<
int> selected;
selected.push_back(acts[0].id);
int lastFinish = acts[0].finish;
for (
int i = 1; i < acts.size(); i++) {
if (acts[i].start >= lastFinish) {
selected.push_back(acts[i].id);
lastFinish = acts[i].finish;
}
}
return selected;
}
Python 实现
def greedy_activity_selector(activities):
"""
贪心活动选择算法
Args:
activities: list of (id, start, finish)
Returns:
list of selected activity ids
"""
activities.sort(key=lambda x: x[2])
selected = [activities[0][0]]
last_finish = activities[0][2]
for act in activities[1:]:
act_id, start, finish = act
if start >= last_finish:
selected.append(act_id)
last_finish = finish
return selected
activities = [(1, 1, 4), (2, 3, 5),
(3, 0, 6), (4, 5, 7),
(5, 3, 8), (6, 5, 9),
(7, 6, 10), (8, 8, 11),
(9, 8, 12), (10, 2, 13)]
result = greedy_activity_selector(activities)
print(f"选中的活动ID: {result}")
print(f"最大活动数量: {len(result)}")
1.2 交换论证法正确性证明
交换论证法证明贪心策略的最优性
设贪心算法选择的活动集合为 G = {g₁, g₂, ..., gₖ}，最优解的活动集合为 O = {o₁, o₂, ..., oₘ}，且按结束时间递增排列。我们要证明 k = m。
证明思路：通过"交换论证"（Exchange Argument），逐步将最优解转换为贪心解而不改变活动数量。
基础步骤：贪心选择的第一个活动 g₁ 是结束时间最早的活动，即 f[g₁] ≤ f[o₁]。因为 g₁ 是所有活动中结束时间最早的。如果 o₁ ≠ g₁，我们可以将 o₁ 替换为 g₁，得到新的最优解 O' = {g₁, o₂, ..., oₘ}。由于 f[g₁] ≤ f[o₁]，g₁ 的结束时间不比 o₁ 晚，所以 O' 中的活动仍然互不重叠且数量不变。
归纳步骤：假设贪心算法已经选择了前 i 个活动 g₁, g₂, ..., gᵢ，并且我们已将最优解的前 i 个活动替换为 g₁, g₂, ..., gᵢ。现在考虑贪心选择的第 i+1 个活动 gᵢ₊₁。由于 gᵢ₊₁ 是在不与 gᵢ 冲突的前提下结束时间最早的活动，而 oᵢ₊₁ 也是在相同约束下选择的活动（但可能不是最早结束的），因此 f[gᵢ₊₁] ≤ f[oᵢ₊₁]。与基础步骤类似的交换论证表明，我们可以将 oᵢ₊₁ 替换为 gᵢ₊₁ 而不影响最优性。
结论：通过归纳，我们可以将最优解 O 逐步转换为贪心解 G，且 m = k。因此贪心算法找到的是最优解。
时间复杂度分析
- 排序：O(n log n)，对所有活动按结束时间排序
- 选择阶段：O(n)，一次线性扫描选出所有兼容活动
- 总时间复杂度：O(n log n)，排序是主导因素
- 空间复杂度：O(1) 或 O(n)，取决于是否需要存储排序后的活动列表
二、加权活动选择问题（Weighted Activity Selection）
问题扩展
在实际应用中，每个活动通常有不同的权重（如收益、优先级等）。加权活动选择问题的目标是选择一组互不重叠的活动，使得总权重最大化。此时，最早的结束时间贪心策略不再适用，因为选择权重高的活动可能比选择多个权重低的活动更优。
2.1 动态规划解法
动态规划状态设计
将所有活动按结束时间排序后，定义：
- dp[i]：前 i 个活动中能获得的最大总权重
- prev[i]：与活动 i 不冲突且结束时间最晚的活动索引（即结束时间 ≤ s[i] 的最大的 j）
状态转移方程：
dp[i] = max(dp[i-1], weight[i] + dp[prev[i]])
其中 prev[i] 可以通过二分查找在 O(log n) 时间内找到，整体时间复杂度为 O(n log n)。
C++ 实现
struct Activity {
int start, finish, weight;
};
int weightedActivitySelect(
vector<Activity>& acts) {
int n = acts.size();
sort(acts.begin(), acts.end(),
[](
const Activity& a,
const Activity& b) {
return a.finish < b.finish;
});
vector<
int> prev(n, -
1);
for (
int i =
0; i < n; i++) {
int lo =
0, hi = i -
1;
while (lo <= hi) {
int mid = lo + (hi - lo) /
2;
if (acts[mid].finish <= acts[i].start) {
if (acts[mid +
1].finish <= acts[i].start)
lo = mid +
1;
else {
prev[i] = mid;
break;
}
}
else {
hi = mid -
1;
}
}
}
vector<
int> dp(n,
0);
dp[
0] = acts[
0].weight;
for (
int i =
1; i < n; i++) {
int include = acts[i].weight;
if (prev[i] != -
1)
include += dp[prev[i]];
dp[i] = max(dp[i -
1], include);
}
return dp[n -
1];
}
Python 实现（含路径回溯）
def weighted_activity_selector(activities):
"""
加权活动选择 - DP + 二分查找
Args:
activities: list of (start, finish, weight)
Returns:
(max_weight, selected_activities)
"""
acts = sorted(enumerate(activities), key=lambda x: x[1][1])
n = len(acts)
finish_times = [acts[i][1][1] for i in range(n)]
prev = [-1] * n
for i in range(n):
start = acts[i][1][0]
lo, hi = 0, i - 1
while lo <= hi:
mid = (lo + hi) // 2
if finish_times[mid] <= start:
prev[i] = mid
lo = mid + 1
else:
hi = mid - 1
dp = [0] * n
choice = [False] * n
dp[0] = acts[0][1][2]
choice[0] = True
for i in range(1, n):
include = acts[i][1][2]
if prev[i] != -1:
include += dp[prev[i]]
exclude = dp[i - 1]
if include > exclude:
dp[i] = include
choice[i] = True
else:
dp[i] = exclude
choice[i] = False
selected = []
i = n - 1
while i >= 0:
if choice[i]:
selected.append(acts[i][0])
i = prev[i]
else:
i -= 1
selected.reverse()
return dp[n - 1], selected
acts = [(1, 4, 5),
(3, 5, 3),
(0, 6, 8),
(5, 7, 6),
(3, 8, 4),
(5, 9, 2),
(6, 10, 7),
(8, 11, 9)]
max_weight, selected = weighted_activity_selector(acts)
print(f"最大权重: {max_weight}")
print(f"选中的活动索引: {selected}")
2.2 二分查找优化详解
为什么需要二分查找？
如果使用线性扫描查找 prev[i]，每次需要 O(n) 时间，总时间复杂度退化为 O(n²)。由于活动已按结束时间排序，finish 数组是单调递增的，这天然适合二分查找。每次查找 prev[i] 只需要 O(log n) 时间，DP 阶段的总体复杂度为 O(n log n)。与排序阶段组合，整体算法复杂度为 O(n log n)。
加权活动选择时间复杂度
- 排序：O(n log n)
- 计算 prev 数组：O(n log n)，每个活动二分查找
- DP 迭代：O(n)
- 总时间复杂度：O(n log n)
- 空间复杂度：O(n) 用于存储 dp, prev, choice 数组
对比未优化的 DP 实现（线性查找 prev）：O(n²)，二分查找将复杂度从二次降到对数线性。
三、区间调度问题族
活动选择问题是区间调度（Interval Scheduling）问题族中的一个基本问题。该问题族包含多个变种，每个都有不同的约束条件和优化目标。
3.1 区间调度问题分类
| 问题类型 |
目标 |
算法 |
时间复杂度 |
| 最大不重叠区间 (Max Non-overlapping Intervals) |
选择最多互不重叠区间 |
最早结束时间贪心 |
O(n log n) |
| 区间分组 (Interval Partitioning) |
最少教室数安排所有课程 |
贪心 + 最小堆 |
O(n log n) |
| 区间覆盖 (Minimum Interval Cover) |
最少区间覆盖目标区间 |
贪心扩展最远覆盖 |
O(n log n) |
| 机器调度 (Machine Scheduling) |
最少机器完成所有任务 |
最早开始时间 + 最小堆 |
O(n log n) |
| 加权区间调度 (Weighted Interval Scheduling) |
最大权重不重叠区间 |
DP + 二分查找 |
O(n log n) |
3.2 区间分组问题（Interval Partitioning）
问题描述
给定 n 个课程（区间），每门课程有固定的上课时间 [s[i], f[i])，需要安排教室使得所有课程都能进行且互不冲突。目标是使用最少的教室数量。
这是经典的"教室调度"问题，等价于求最大重叠深度——即在任何时间点同时进行的最多课程数量。
贪心算法：最早开始时间优先 + 最小堆
def interval_partitioning(intervals):
"""
区间分组 - 最少教室数量
Args:
intervals: list of (start, finish)
Returns:
(min_classrooms, assignment)
"""
intervals.sort(key=lambda x: x[0])
import heapq
rooms = []
assignment = []
next_room_id = 0
for start, finish in intervals:
if rooms and rooms[0][0] <= start:
finish_time, room_id = heapq.heappop(rooms)
assignment.append(room_id)
heapq.heappush(rooms, (finish, room_id))
else:
room_id = next_room_id
next_room_id += 1
assignment.append(room_id)
heapq.heappush(rooms, (finish, room_id))
return len(rooms), assignment
算法正确性关键
- 按开始时间处理保证了所有区间以时间顺序扫描
- 最小堆始终保持当前占用教室中最早结束时间的教室在堆顶
- 如果最早结束的教室在上课开始时已空闲，则复用；否则必须开新教室
- 最少教室数 = 最大重叠深度 = 所有时间点上重叠区间的最大数量
- 时间复杂度：O(n log n)，每个区间一次堆操作
3.3 区间覆盖问题（Minimum Interval Cover）
问题描述
给定一个目标区间 [T_start, T_end] 和 n 个可用区间 [s[i], f[i]]，选择最少数量的区间覆盖整个目标区间。每个可用区间可以部分覆盖目标区间，且区间之间可以重叠。
算法策略：每次在当前覆盖终点左侧的区间中，选择向右延伸最远的区间。
区间覆盖贪心算法
def min_interval_cover(target_start, target_end, intervals):
"""
最少区间覆盖目标区间
Args:
target_start: 目标区间起点
target_end: 目标区间终点
intervals: list of (start, finish)
Returns:
list of selected intervals (or None if impossible)
"""
intervals.sort(key=lambda x: x[0])
selected = []
covered_until = target_start
i = 0
n = len(intervals)
while covered_until < target_end:
best = -1
farthest = covered_until
while i < n and intervals[i][0] <= covered_until:
if intervals[i][1] > farthest:
farthest = intervals[i][1]
best = i
i += 1
if best == -1:
return None
selected.append(intervals[best])
covered_until = farthest
return selected
区间覆盖算法正确性证明
设贪心算法选择的区间序列为 G = {g₁, g₂, ..., gₖ}，覆盖的范围为 [T_start, far(g₁), far(g₂), ..., T_end]。设最优解为 O = {o₁, o₂, ..., oₘ}。
归纳假设：贪心算法在第 t 步后的覆盖范围 ≥ 最优解在第 t 步后的覆盖范围。
基础步骤：第一步，贪心算法在所有覆盖 T_start 的区间中选择延伸最远的区间 g₁，所以 far(g₁) ≥ far(o₁)。
归纳步骤：假设前 t-1 步后，贪心覆盖到 far(g_{t-1}) ≥ far(o_{t-1})。在第 t 步，贪心算法在所有起点 ≤ far(g_{t-1}) 的区间中选最远的。由于 far(o_{t-1}) ≤ far(g_{t-1})，所以 o_t 的起点肯定 ≤ far(g_{t-1})，因此贪心算法在第 t 步的可选集合包含 o_t。贪心选择最远的区间，所以 far(g_t) ≥ far(o_t)。
结论：贪心算法使用的区间数量 ≤ 最优解使用的区间数量，因此贪心算法是最优的。
四、任务调度（Job Scheduling）
问题背景
任务调度问题（Job Scheduling / Sequencing）研究如何安排一组任务在单台或多台机器上执行，以优化某个目标函数。这是一个在操作系统、生产调度、项目管理等领域有广泛应用的经典问题。
4.1 最小化最大延迟（Minimizing Maximum Lateness）
问题定义
给定 n 个任务，每个任务 i 有处理时间 p[i] 和截止时间 d[i]。所有任务在单台机器上按某个顺序执行（不可抢占）。设任务 i 的完成时间为 C[i]，则其延迟 L[i] = max(0, C[i] - d[i])。目标是最小化最大延迟 L_max = max L[i]。
4.2 EDD 规则（Earliest Due Date）
EDD 算法：按截止时间最早优先排序
EDD（Earliest Due Date）规则由 Jackson 于 1955 年提出：将任务按截止时间从小到大排列，按此顺序执行即可最小化最大延迟。
struct Job {
int id;
int processing_time;
int deadline;
};
void EDD_Schedule(vector<Job>& jobs) {
sort(jobs.begin(), jobs.end(),
[](const Job& a, const Job& b) {
return a.deadline < b.deadline;
});
int time = 0;
int max_lateness = 0;
for (const auto& job : jobs) {
time += job.processing_time;
int lateness = max(0, time - job.deadline);
max_lateness = max(max_lateness, lateness);
printf("任务 %d: 完成时间=%d, 截止时间=%d, 延迟=%d\n",
job.id, time, job.deadline, lateness);
}
printf("最大延迟: %d\n", max_lateness);
}
EDD 规则最优性证明（交换论证）
假设最优解 S 中任务不是按截止时间排序的，则存在相邻任务 i 和 j，使得 d[i] > d[j] 但 i 排在 j 之前。我们证明交换这两个任务不会增加最大延迟。
交换前：设任务 i 和 j 开始前的完成时间为 T。
- C[i] = T + p[i], L[i] = max(0, T + p[i] - d[i])
- C[j] = T + p[i] + p[j], L[j] = max(0, T + p[i] + p[j] - d[j])
交换后：将 i 和 j 互换。
- C'[j] = T + p[j], L'[j] = max(0, T + p[j] - d[j])
- C'[i] = T + p[j] + p[i], L'[i] = max(0, T + p[j] + p[i] - d[i])
由于 d[i] > d[j]，交换前 L[j] ≥ L[i]（因为 j 截止更早但排更晚）。交换后 i 的完成时间不变（C'[i] = C[i]），而 j 的完成时间提前了（C'[j] < C[j]），所以 L'[j] ≤ L[j] 且 L'[i] = L[i]。因此交换后最大延迟不会增加。
通过有限次交换，可以将任意最优解转换为 EDD 顺序，且最大延迟不增加，因此 EDD 是最优的。
4.3 Moore-Hodgson 算法（最小化延迟任务数）
问题变种
与最小化最大延迟不同，Moore-Hodgson 算法解决的是最小化延迟任务数量问题：在单台机器上安排任务，目标是最小化超过截止时间的任务数。
算法步骤：
- 按 EDD 规则（截止时间最早优先）执行所有任务
- 如果当前任务导致延迟，从已执行的任务中选择处理时间最长的任务移除
- 重复直到所有剩余任务都能按时完成
Moore-Hodgson 算法实现
def moore_hodgson(jobs):
"""
最小化延迟任务数
Args:
jobs: list of (processing_time, deadline)
Returns:
(min_late_jobs, schedule)
"""
jobs.sort(key=lambda x: x[1])
import heapq
scheduled = []
time = 0
late_count = 0
for p, d in jobs:
time += p
heapq.heappush(scheduled, -p)
if time > d:
longest = -heapq.heappop(scheduled)
time -= longest
late_count += 1
on_time_count = len(scheduled)
return late_count, on_time_count
4.4 Horn 算法（最小化加权完成时间之和）
问题定义
当每个任务有权重 w[i] 时，一个常见的优化目标是最小化加权完成时间之和 Σ(w[i] × C[i])。Horn 算法通过"最短处理时间优先"（Shortest Processing Time, SPT）规则解决该问题。
Smith 规则：按 p[i]/w[i] 的比值从小到大排序（即"权重密度"从高到低）。对于单位权重的特例，简化为按处理时间从小到大排序（SPT）。
Smith 规则（最小化 Σ w[i]C[i]）
def smith_rule_schedule(jobs):
"""
Smith规则：按 p[i]/w[i] 升序排列
最小化加权完成时间之和 Σ(w[i] × C[i])
"""
jobs.sort(key=lambda x: x[0] / x[1])
time = 0
total_weighted_completion = 0
for p, w in jobs:
time += p
total_weighted_completion += w * time
return total_weighted_completion
任务调度算法复杂度总结
| 算法 |
目标 |
时间复杂度 |
排序规则 |
| EDD（Jackson） |
最小化最大延迟 |
O(n log n) |
按截止时间升序 |
| Moore-Hodgson |
最小化延迟任务数 |
O(n log n) |
EDD + 移除最长任务 |
| SPT |
最小化总完成时间 |
O(n log n) |
按处理时间升序 |
| Smith 规则 |
最小化加权总完成时间 |
O(n log n) |
按 p[i]/w[i] 升序 |
| Horn 算法 |
可抢占最小化 ΣwC |
O(n log n) |
SRPT（最短剩余时间） |
五、多机调度问题（Multiprocessor Scheduling）
问题定义
多机调度问题（Multiprocessor Scheduling / Load Balancing）是一个经典的 NP-难问题。给定 m 台相同的机器和 n 个任务（每个任务有处理时间 p[i]），目标是将任务分配到 m 台机器上，使得最大完工时间（makespan）最小化。该问题在学术上被称为 P || C_max。
5.1 贪心近似算法：List Scheduling
Greedy List Scheduling 算法
Graham 于 1966 年提出的贪心算法：维护每个机器的当前负载，每次将下一个任务分配给当前负载最小的机器。
def list_scheduling(machines, processing_times):
"""
Graham's List Scheduling 贪心近似算法
Args:
machines: 机器数量 m
processing_times: list of processing times
Returns:
(makespan, assignment)
"""
import heapq
loads = [(0, i) for i in range(machines)]
heapq.heapify(loads)
assignment = [None] * len(processing_times)
for i, p in enumerate(processing_times):
load, machine = heapq.heappop(loads)
assignment[i] = machine
heapq.heappush(loads, (load + p, machine))
makespan = max(loads, key=lambda x: x[0])[0]
return makespan, assignment
近似比分析
List Scheduling 算法确保：
- makespan ≤ (2 - 1/m) × OPT，其中 OPT 是最优解
- 设 L* 为最优 makespan，则：L* ≥ max(max p[i], Σp[i]/m)
- 贪心算法的 makespan ≤ max(Σp[i]/m + max p[i]) ≤ 2 × OPT
- 这个界是紧的：存在实例使得算法恰好达到 2 - 1/m 倍
5.2 LPT 算法（Longest Processing Time First）
LPT 算法：任务按处理时间降序排列再调度
Graham 证明了将任务按处理时间从大到小排序后再进行 List Scheduling，可以显著改进近似比。
def lpt_scheduling(machines, processing_times):
"""
LPT（最长处理时间优先）+ List Scheduling
近似比: 4/3 - 1/(3m)
"""
sorted_times = sorted(enumerate(processing_times),
key=lambda x: x[1], reverse=True)
import heapq
loads = [(0, i) for i in range(machines)]
heapq.heapify(loads)
assignment = [None] * len(processing_times)
for orig_idx, p in sorted_times:
load, machine = heapq.heappop(loads)
assignment[orig_idx] = machine
heapq.heappush(loads, (load + p, machine))
makespan = max(loads, key=lambda x: x[0])[0]
return makespan, assignment
LPT 算法近似比证明
定理：LPT 算法的近似比为 4/3 - 1/(3m)。
证明思路：
- 设 LPT 的 makespan 为 C_max，最优解为 C*。C* ≥ max{max p[i], Σp[i]/m}。
- 假设 LPT 的 makespan 由机器 M_k 上的任务 j 决定，且 j 是最后分配到 M_k 上的任务。
- 由于 LPT 按降序排列，分配到 M_k 之前的所有任务（含 j）中，j 的处理时间是最短的。
- 在将 j 分配到 M_k 之前，M_k 的负载 ≤ 所有机器的平均负载（因为贪心选择最小负载机器），即 ≤ (Σp[i] - p[j]) / m。
- 因此 C_max = (Σp[i] - p[j]) / m + p[j] = Σp[i]/m + (1 - 1/m)p[j]。
- 如果 p[j] ≤ C*/3，则 C_max ≤ Σp[i]/m + (1 - 1/m)C*/3 ≤ C* + (1 - 1/m)C*/3 = (4/3 - 1/(3m))C*。
- 如果 p[j] > C*/3，则除了 j 外，最多还有 m-1 个任务的处理时间 ≥ p[j]（因为 LPT 排序）。因此所有任务数 ≤ m，LPT 给出最优解。
5.3 多机调度算法对比
| 算法 |
近似比 |
时间复杂度 |
特点 |
| List Scheduling（任意顺序） |
2 - 1/m |
O(n log m) |
在线算法，不需要知道全部任务 |
| LPT（降序排列） |
4/3 - 1/(3m) |
O(n log n + n log m) |
离线算法，先排序再调度 |
| PTAS（多项式时间近似方案） |
1 + ε |
依赖于 ε |
理论上可任意接近最优解 |
多机调度的 NP-难性质
多机调度问题 P || C_max 是NP-难的（即使只有 2 台机器也是弱 NP-难的，可通过划分问题归约证明）。这意味着除非 P = NP，否则不存在多项式时间的最优算法。因此贪心近似算法是实际应用中合理的选择。
- 对于 m ≤ 2（特殊情况），存在伪多项式时间最优算法（DP）
- 对于固定 m，可以通过 DP 在 O(n × (Σp)^(m-1)) 时间内求解
- 实际系统中，LPT 算法由于其简单性和良好的近似比而被广泛使用