输入说明
-
n—— 活动数量 -
s[1…n]— 第 i 个活动的开始时间 (start) -
f[1…n]— 第 i 个活动的结束时间 (finish)
前置要求：数组已按
f从小到大排好序
（若没排，先调用sortByFinishTime()，复杂度O(n log n)）
伪代码（逐行注释版）
GreedyActivitySelection(s, f, n)A ← ∅ // A：最终被选中的活动下标集合// —— 第 1 步：先选最早结束的活动 —— choose ← 1 // 已排序后，索引 1 的活动结束最早A ← A ∪ {choose} // 放入解集lastFinish ← f[choose] // 记录上一次已选活动的结束时间// —— 第 2 步：从第 2 个活动开始往后扫描 —— for i ← 2 to n do // 依序考察每个活动if s[i] ≥ lastFinish then // 若当前活动的开始时间不早于上一次结束A ← A ∪ { i } // 选中它！lastFinish ← f[i] // 更新“最近一次结束时间”// —— 扫描完毕，A 就是最大兼容子集 —— return A
变量回顾
| 变量名 | 含义 |
|---|---|
A | 当前已确定选入的活动下标集合 |
choose | 第一轮选中的活动（结束最早） |
lastFinish | 最近一次被选中活动的结束时间 |
i | for-loop 的活动下标指针（从 2 到 n） |
执行示意（小样本）
编号: 1 2 3 4
s[]: 1 3 0 5
f[]: 4 5 6 7 ← 已按 f 升序排好起步: A = {1}, lastFinish = 4
i=2: s[2]=3 < 4 → 不选
i=3: s[3]=0 < 4 → 不选
i=4: s[4]=5 ≥ 4 → 选 4, A = {1,4}, lastFinish=7
结束: 返回 {1,4}
复杂度
-
排序阶段（若需要）：
O(n log n) -
主循环扫描 ：
O(n) -
总时间 ：
O(n log n) -
额外空间 ：
O(1)（仅常数变量）
这样写就非常直观了：
-
先选 “结束时间最早的活动”
-
再扫 其后所有活动，凡是开始时间 ≥ 最近结束时间的就加入
-
一趟扫描就搞定！
)
