贪心算法

贪心思维

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

何时考虑贪心

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

贪心 vs DP

区间调度

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

// 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（最少房间数，用堆或差分数组）

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

跳跃游戏

跳跃游戏：维护当前能到达的最远位置 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（最少跳数）

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

其他经典贪心

典型题目

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

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