贪心算法

贪心思维框架

每一步做当前看起来最好的选择，不回溯。正确性依赖问题结构，不能凭直觉。面试答题建议：

猜贪心策略（排序键、优先队列、计数）。

举反例尝试推翻。

用交换论证：任意最优解可通过交换变为贪心解且不更差。

区间类（高频）

最多不相交区间：按结束时间升序，能选就选当前（结束最早留最多空间）。

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])
    end = float("-inf")
    removed = 0
    for s, e in intervals:
        if s < end:
            removed += 1
        else:
            end = e
    return removed

合并区间：按起点排序，扫描合并。插入区间：先合并再插入。

分配与覆盖

跳跃游戏：维护能到达的最远 maxReach，遍历中若 i > maxReach 失败，否则更新。跳跃游戏 II 用 BFS 层或贪心记录当前层最远与下一层最远。

分发饼干 / 分糖果：排序后双指针或小根堆满足「最小够用」。

哈夫曼与堆贪心

合并果子、连接绳子：每次合并代价最小的两个，用小根堆，总代价最小（哈夫曼思想）。

import heapq
def min_merge_cost(arr):
    heapq.heapify(arr)
    cost = 0
    while len(arr) > 1:
        a = heapq.heappop(arr)
        b = heapq.heappop(arr)
        cost += a + b
        heapq.heappush(arr, a + b)
    return cost

与 DP 的边界

• 0-1 背包不能贪心容量（价值密度会错）。
• 硬币找零面值任意时贪心可能错，需 DP；特殊面值（如 1,5,10,25）可贪心。

| 题型 | 贪心信号 | |---|---| | 调度、截止日期 | 排序 + 堆 | | 区间选点/覆盖 | 端点排序 | | 字符串重建 | 计数 + 优先队列 | | 股票多次交易 | 累加正差 |

推荐练习：435、452、55、45、621、767。写解法时一句话点明「为何局部最优不会损害全局」，是面试加分项。