贪心算法

贪心思维

贪心算法在每个决策点选择当前看起来最好的选项，且不回退。正确性依赖「贪心选择性质」：局部最优选择能导向全局最优。证明方法通常是交换论证（exchange argument）：假设最优解与贪心解不同，交换两者的某个决策不会让解变差，矛盾。

何时考虑贪心

• 问题有排序/优先级自然语义（最早结束时间、最小/最大值优先）
• 子问题之间无依赖（不需要「回头」更新之前的决策）
• 能构造交换论证或归纳证明
• 穷举/DP 复杂度太高，但贪心直觉显然正确

贪心 vs DP

交换论证

交换论证（Exchange Argument）是证明贪心算法正确性的标准方法。思路：假设存在最优解 OPT，它在某一步与贪心解 G 不同，则将 OPT 的那一步替换为贪心的选择，证明替换后的解不比 OPT 差。反复替换直到 OPT 变成 G，从而证明 G 也是最优解。

// Exchange Argument — Interval Scheduling (LC 435)
// Claim: sorting by end time and greedily picking is optimal.
//
// Proof:
//   Let G = greedy solution, OPT = any optimal solution.
//   Find the first position i where they differ.
//   OPT[i] = B  (some interval);  G[i] = A  (end_A <= end_B by sort order).
//   Form OPT' by replacing B with A:
//     - A doesn't extend further right than B (end_A <= end_B).
//     - Future intervals conflict no more with A than with B.
//   |OPT'| = |OPT|, and OPT' agrees with G one step further.
//   Repeat all the way → G is at least as good as OPT.  □

通用证明框架

• 1. 假设最优解 OPT 与贪心解 G 不同，找第一个差异位置 i
• 2. OPT 在位置 i 选择了 B；贪心在位置 i 选择了 A（A 更优或等优）
• 3. 将 OPT 中的 B 替换为 A，构造 OPT'
• 4. 证明 OPT' 合法且不比 OPT 差（关键步骤）
• 5. 重复替换——逐步将 OPT 转化为 G，故 G 的质量 ≥ OPT

以区间调度为例（LC 435）：按结束时间排序后，贪心每步选结束最早的合法区间 A。若 OPT 在同一位置选了结束更晚的 B：将 B 换成 A，A 结束更早，后续区间与 A 冲突只会更少，所以替换后选取数量不变甚至更多——贪心正确。

区间调度

经典贪心：按结束时间升序排列所有区间，依次选取不与上一个冲突的区间。这保证选取数量最多（剩余时间最多）。合并区间则是按起始时间排序后扫描合并。

// LC 435 — Non-overlapping Intervals (max non-overlapping = total - removals)
int eraseOverlapIntervals(vector<pair<int,int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](auto& a, auto& b){ return a.second < b.second; }); // sort by end
    int count = 0, end = INT_MIN;
    for (auto& [s, e] : intervals) {
        if (s >= end) { count++; end = e; } // non-overlapping: select it
    }
    return (int)intervals.size() - count;
}

典型题目

• 435. 无重叠区间（最少移除数 = 总数 - 最多非重叠数）
• 452. 用最少数量的箭引爆气球（与 435 同一核心）
• 56. 合并区间（按起点排序后合并）
• 253. 会议室 II（最少房间数，用堆或差分数组）

排序关键字：「最多不重叠区间」按结束时间升序；「合并区间」按起始时间升序；「最少箭」与「最多不重叠」等价，按结束时间升序。

区间问题详解

区间问题的排序关键字取决于目标：最多不重叠区间按结束时间升序，合并区间按起始时间升序。选错排序方式会导致贪心失效。

为什么是结束时间？

按结束时间排序，每次选择都能留给后续区间尽量多的空间。若改按起始时间排序：先选的区间可能跨度很长，即使起始最早，也会封堵大量后续区间——结果更差。贪心只在按结束时间排时才能通过交换论证。

// LC 56 — Merge Intervals
vector<pair<int,int>> merge(vector<pair<int,int>>& v) {
    sort(v.begin(), v.end());          // sort by start time
    vector<pair<int,int>> res;
    for (auto& [s, e] : v) {
        if (!res.empty() && s <= res.back().second)
            res.back().second = max(res.back().second, e);
        else
            res.push_back({s, e});
    }
    return res;
}

两种排序方式对比

跳跃游戏

跳跃游戏：维护当前能到达的最远位置 maxReach，遍历数组，若当前下标超过 maxReach 则无法到达终点。最少跳数：维护当前跳结束位置 curEnd 和下一跳能到的最远 farthest，到达 curEnd 时跳数 +1。

// LC 55 — Jump Game
bool canJump(vector<int>& nums) {
    int maxReach = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (i > maxReach) return false;
        maxReach = max(maxReach, i + nums[i]);
    }
    return true;
}

// LC 45 — Jump Game II (minimum jumps)
int jump(vector<int>& nums) {
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i + 1 < (int)nums.size(); i++) {
        farthest = max(farthest, i + nums[i]);
        if (i == curEnd) { jumps++; curEnd = farthest; }
    }
    return jumps;
}

典型题目

• 55. 跳跃游戏（判断能否到达终点）
• 45. 跳跃游戏 II（最少跳数）

贪心正确性：每次跳到能覆盖最远的落点，比任何其他策略跳得更远或相同——交换论证可证。

贪心 vs DP 对比

贪心并非万能。当问题缺乏「贪心选择性质」时，局部最优无法推导全局最优，必须改用 DP。

反例：贪心失效

零钱兑换：硬币面额 [1, 3, 4]，目标 6。贪心（每次选最大面额）：4 + 1 + 1 = 3 枚；最优：3 + 3 = 2 枚。贪心给出非最优解，因为选 4 之后破坏了后续的最优组合。

对比总结

判断规则：能构造交换论证或归纳证明 → 贪心；存在「牺牲当前最优以换取更好全局结果」的场景 → DP。

// LC 621 — Task Scheduler (formula approach)
// Most frequent task sets the frame count; idle slots fill the gaps.
// Frames: (maxF - 1) blocks of (n+1) slots + final partial block.
int leastInterval(vector<char>& tasks, int n) {
    int freq[26] = {};
    for (char c : tasks) freq[c - 'A']++;
    int maxF = *max_element(freq, freq + 26);
    int maxCount = count(freq, freq + 26, maxF);
    return max((int)tasks.size(), (maxF - 1) * (n + 1) + maxCount);
}

其他经典贪心

典型题目

• 455. 分发饼干（排序后双指针匹配）
• 134. 加油站（从某点出发绕圈，总油量 ≥ 0 则有解）
• 406. 根据身高重建队列（按身高降序 + 按 k 插入）
• 621. 任务调度器（频次最高的任务决定等待时间）
• 179. 最大数（自定义比较器：拼接后字典序大的在前）

排序比较器：179 题的比较器：比较 a+b 与 b+a 的字典序（拼接两个字符串再比较），不能直接用数字比较。