算法刷题系列（二十六）：贪心算法——从局部选择到正确性证明

算法刷题系列（二十六）：贪心算法——从局部选择到正确性证明

贪心算法每一步都作出一个当下看来有利的选择，并且通常不回头修改。实现可能很短，证明却不能省略：局部最优选择并不自动等于全局最优。本文用区间调度说明如何把选择规则、交换论证和不变式连起来。

一、例子：最多安排多少个互不重叠活动

每个活动用半开区间 [start, end) 表示。若前一个活动在 4 结束，另一个从 4 开始，两者不重叠。目标是在所有活动中选出尽可能多的互不冲突活动。

例如 [1,4)、[3,5)、[4,7)、[6,8)、[7,9)。按结束时间从早到晚排序，先选 [1,4)，再选 [4,7)，最后选 [7,9)，总数为 3。

二、贪心规则与交换证明

规则是：在当前可选活动中，选择结束最早的活动。为什么不是选择开始最早或时长最短？因为结束越早，留给后续活动的可用时间越多；但这个直觉需要证明。

设某个最优方案的第一个活动是 A，贪心选择是 G。由于 G 结束不晚于任何可行首活动，特别是 end(G) <= end(A)。把最优方案中的 A 换成 G，后续活动原本在 A 结束后才开始，因此也会在 G 结束后开始。替换不减少活动数量，于是存在一个以 G 开头的最优方案。删除已选的 G 后，剩余问题仍是同类的区间调度问题。逐步重复可证贪心解最优。

三、Java 实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Main {
    static List<int[]> selectActivities(int[][] activities) {
        int[][] sorted = new int[activities.length][2];
        for (int i = 0; i < activities.length; i++) {
            if (activities[i] == null || activities[i].length != 2
                    || activities[i][0] > activities[i][1]) {
                throw new IllegalArgumentException("each activity needs start <= end");
            }
            sorted[i] = Arrays.copyOf(activities[i], 2);
        }
        Arrays.sort(sorted, Comparator
                .comparingInt((int[] item) -> item[1])
                .thenComparingInt(item -> item[0]));

        List<int[]> chosen = new ArrayList<>();
        boolean hasPrevious = false;
        int previousEnd = 0;
        for (int[] activity : sorted) {
            if (!hasPrevious || activity[0] >= previousEnd) {
                chosen.add(activity);
                previousEnd = activity[1];
                hasPrevious = true;
            }
        }
        return chosen;
    }

    public static void main(String[] args) {
        List<int[]> chosen = selectActivities(new int[][]{
                {1, 4}, {3, 5}, {4, 7}, {6, 8}, {7, 9}
        });
        assert chosen.size() == 3;
        assert chosen.get(0)[0] == 1 && chosen.get(1)[0] == 4
                && chosen.get(2)[0] == 7;
        assert selectActivities(new int[0][2]).isEmpty();
    }
}

四、Python 实现

from typing import Optional

def select_activities(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
    for start, end in activities:
        if start > end:
            raise ValueError("each activity needs start <= end")

    ordered = sorted(activities, key=lambda activity: (activity[1], activity[0]))
    chosen: list[tuple[int, int]] = []
    previous_end: Optional[int] = None
    for start, end in ordered:
        if previous_end is None or start >= previous_end:
            chosen.append((start, end))
            previous_end = end
    return chosen

assert select_activities([(1, 4), (3, 5), (4, 7), (6, 8), (7, 9)]) == [
    (1, 4), (4, 7), (7, 9)
]
assert select_activities([]) == []

五、复杂度、边界与常见误判

排序耗时 O(n log n)，扫描耗时 O(n)；输出至多 O(n)。空活动集合返回空结果。相同结束时间的次序不影响最优性，示例以开始时间作稳定的次级排序。零长度区间在半开区间约定下可与同一时刻开始或结束的区间兼容；若题目使用闭区间，兼容条件需改为严格大于。

另一个常见误区是把“贪心”当作证明。比如硬币面值并非特定规范体系时，每次拿最大硬币未必能用最少枚数；局部规则可能卡在后续选择。对新问题，应寻找交换论证、最优子结构或可维持的安全不变式；若证明不成立，考虑动态规划或其他方法。

小结与衔接

区间调度的早结束规则之所以正确，是因为任意最优解都能交换成包含这次贪心选择的解。贪心强调决策与证明。下一篇回到树结构：递归同样需要明确的子问题定义，但它不是贪心选择，而是把节点问题拆成子树问题。