• 思想：从起点到终点，始终做当下“看起来最好”的选择（局部最优），不回溯，逐步构造解。

• 适用前提：

  1. 贪心选择性质：存在某个最优解，它的第一步与贪心选择一致；

  2. 最优子结构：选完这一步后，余下子问题的最优解与原问题的最优解可拼接。

• 正确性证明常用法：

  • 交换论证：把任意最优解通过交换步骤改造成以贪心选择开头的最优解；

  • 数学归纳/反证，或借用结构理论（如拟阵）与次模性。

活动安排问题

思路（贪心策略）

把所有活动按结束时间从小到大排序；从前往后扫，遇到一个活动的开始时间不早于上一个已选活动的结束时间，就把它选入。
直觉：越早结束，越不“占坑”，为后续留下最大空间。

正确性证明

贪心选择性质（交换论证）

设活动按结束时间排序为 $a_1,a_2,\dots,a_n$ 且 $f_1 \le f_2 \le \dots \le f_n$​。
令 $G$为贪心解，首先选择 $a_1$​。令 $O$ 为任一最优解（活动数最多），其第一项设为 $a_k$​。

• 若 $a_k = a_1$​，则与贪心一致。

• 若 $a_k \ne a_1$，由于 $f_1 \le f_k$​，把 $O$ 的第一项 $a_k$ ​ 用 $a_1$​ 替换，得到解 $O'$。
  对 $O$ 中其余活动 $a_{k+1}, a_{k+2}, \dots$，它们的开始时间均满足 $s \ge f_k \ge f_1$，因此与 $a_1$​ 仍相容，活动总数不变。
  于是存在一个最优解以 $a_1$​ 开头。

结论：选择“最早结束”的活动不会降低最优性，贪心第一步是安全的。

最优子结构（归纳）

选定 $a_1$​后，剩余可选活动集合为 $S'=\{\,a_i \mid s_i \ge f_1\,\}$。
原问题的一个最优解等于 $\{a_1\} \cup$在 $S'$ 上的最优解。
对 $S'$ 递用同样的“按结束时间最早”规则，结合数学归纳法，贪心算法整体最优。

伪代码

# 输入：activities = [(s1, f1), (s2, f2), ..., (sn, fn)]
# 约定：相容当且仅当 s_j >= f_i 或 s_i >= f_j（允许“贴边”）

def select_activities(activities):
    # 1) 按结束时间升序
    acts = sorted(activities, key=lambda x: x[1])

    A = []                # 选择的最大相容集合
    last_finish = -inf    # 上一个入选活动的结束时间

    for s, f in acts:
        if s >= last_finish:
            A.append((s, f))
            last_finish = f

    return A              # A 的长度即最多能安排的活动数

复杂度

时间复杂度： $\mathcal{O}(nlogn)$

迪杰斯特拉算法