贪心算法：核心原理与区间调度

贪心算法的本质

贪心算法在每一步都做出当前看来最优的局部选择，最终期望得到全局最优解。

这和人类的直觉决策非常相似：收拾书桌时，你会先把最大的物件归位，剩余空间就好安排了。贪心就是这种"先把大问题解决掉，小问题自然迎刃而解"的思维。

贪心 vs 动态规划

两者都基于最优子结构，但贪心不回头：

贪心选择性是关键：某一步的局部最优选择，不会破坏后续步骤的最优解空间。证明方法通常是交换论证法（Exchange Argument）：假设最优解中有一个不符合贪心策略的选择，将其替换为贪心选择后，结果不变差。

区间调度：活动选择问题

问题描述

有 n 个活动，每个活动有开始时间和结束时间。同一时间只能做一件事，求最多能参加几个活动（LeetCode 435 的对偶问题）。

直觉：想尽可能参加更多活动，就要尽快结束当前活动，给后面的活动留出时间——按结束时间排序，贪心选结束最早的不冲突活动。

贪心策略的正确性

用交换论证法：假设最优解中第一个活动是 A，结束时间晚于贪心选择的活动 B。把 A 换成 B 后，B 结束更早，不会影响后续活动的选择，因此结果不变差。

无重叠区间（LeetCode 435）

删除最少区间数，使剩余区间互不重叠。

等价转化：最少移除数 = 总数 - 最多不重叠区间数。

// 贪心：按右端点排序，尽量保留结束早的区间
int eraseOverlapIntervals(int[][] intervals) {
    // 按结束时间（右端点）升序排列
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    
    int kept = 0;          // 已保留的不重叠区间数
    int end = Integer.MIN_VALUE;  // 上一个保留区间的右端点
    
    for (int[] interval : intervals) {
        if (interval[0] >= end) {  // 当前区间不与上一个重叠
            kept++;
            end = interval[1];    // 更新右端点
        }
        // 否则跳过（保留已有的，因为它结束更早）
    }
    return intervals.length - kept;
}

模拟过程（示例：[[1,2],[2,3],[3,4],[1,3]]）：

按右端点排序后：[1,2] [2,3] [1,3] [3,4]
                   ↑
              end = MIN

选 [1,2]：0 >= MIN → kept=1, end=2
选 [2,3]：2 >= 2  → kept=2, end=3
选 [1,3]：1 < 3   → 跳过（与[2,3]重叠）
选 [3,4]：3 >= 3  → kept=3, end=4

最多保留 3 个 → 最少移除 4-3 = 1 个

复杂度：O(n log n) 排序 + O(n) 扫描。

区间合并（LeetCode 56）

合并所有重叠区间。

策略：按左端点排序，依次检查当前区间与上一个是否重叠，重叠则合并（取较大右端点）。

int[][] merge(int[][] intervals) {
    // 按左端点升序排列
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    
    List<int[]> res = new ArrayList<>();
    int[] curr = intervals[0];  // 当前待合并区间
    
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= curr[1]) {
            // 重叠：更新右端点（取较大者）
            curr[1] = Math.max(curr[1], intervals[i][1]);
        } else {
            // 不重叠：保存当前区间，切换到下一个
            res.add(curr);
            curr = intervals[i];
        }
    }
    res.add(curr);  // 别忘最后一个区间
    return res.toArray(new int[0][]);
}

模拟过程（示例：[[1,3],[2,6],[8,10],[15,18]]）：

排序后（已有序）
curr = [1,3]
   → [2,6]: 2 <= 3，重叠，curr = [1,6]
   → [8,10]: 8 > 6，不重叠，保存[1,6]，curr = [8,10]
   → [15,18]: 15 > 10，不重叠，保存[8,10]，curr = [15,18]
最后保存[15,18]

结果：[[1,6],[8,10],[15,18]]

用最少箭射气球（LeetCode 452）

坐标轴上有 n 个气球（用区间表示），一支箭射穿所有覆盖该 x 坐标的气球，求最少箭数。

这道题和区间调度高度相似：不需要换箭 = 气球区间相互重叠。

策略：按右端点排序，贪心地把箭射在每组重叠气球的最右端（留最大余地覆盖后面的气球）。

int findMinArrowShots(int[][] points) {
    // 按右端点升序排序
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    
    int arrows = 1;
    int shotAt = points[0][1];  // 第一支箭射在第一个气球的右端
    
    for (int i = 1; i < points.length; i++) {
        if (points[i][0] > shotAt) {  // 当前气球在箭的右边，需补一箭
            arrows++;
            shotAt = points[i][1];
        }
        // 否则当前箭也能覆盖（左端 <= shotAt <= 右端）
    }
    return arrows;
}

与无重叠区间的对比：

贪心的证明框架

绝大多数区间贪心题都用交换论证法证明：

1. 设贪心解为 G，最优解为 OPT
2. 找出 G 和 OPT 中第一个不同的选择
3. 将 OPT 中该选择替换为贪心选择 → 得到 OPT'
4. 证明 OPT' 的效果不比 OPT 差
5. 重复步骤 2-4，直到 OPT 完全变成 G → G 也是最优解

常见贪心排序依据：

• 按结束时间：区间调度、射气球
• 按频率：哈夫曼编码、任务调度
• 按差值（gas-cost）：加油站问题