贪心算法

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

• 适用前提：

  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)

迪杰斯特拉算法