贪心算法

是什么让算法变得贪婪？

贪心算法构建一个解决方案一次一步，总是选择现在看起来最好的选项 - 而不重新考虑过去的选择。没有回头路，没有向前看。

当两个属性成立时它起作用：

1. 贪婪选择属性 - 局部最优选择导致全局最优解。
2. 最优子结构 - 每次选择后剩下的问题是同一问题的较小实例。

活动选择 - 经典示例

给定一组具有开始和结束时间的活动，选择不重叠活动的最大数量。

贪心策略： 按结束时间排序，始终选择最早完成的活动。

def max_activities(intervals):
    intervals.sort(key=lambda x: x[1])
    count, end = 0, 0
    for s, e in intervals:
        if s >= end:
            count += 1
            end = e
    return count

为什么这有效？选择最早完成的活动可以为未来的活动留下最大的空间。没有其他选择可以做得更好。

霍夫曼编码 - 概念

通过重复合并两个最低频率符号来构建最佳的无前缀二进制代码。这是贪婪的：在每一步，合并最便宜的对。结果是一棵树，其中频繁的符号得到短代码。

跳跃游戏

给定一个数组，其中 nums[i] 是从索引 i 开始的最大跳转长度，确定是否可以到达最后一个索引。

贪婪方法： 跟踪迄今为止可到达的最远索引。从左到右扫描 - 如果落后，则返回 false。

def can_jump(nums):
    farthest = 0
    for i, jump in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + jump)
    return True

加油站

沿着有加油站的环形路线行驶。在i站，您获得gas[i]燃料并花费cost[i]到达下一站。找到可以让您完成环路的起始站，或返回−1。

贪婪洞察力：如果总天然气≥总成本，则存在解决方案。追踪持续盈余；每当它低于零时，答案必须在该点之后开始。

任务调度器

在相同任务之间安排冷却时间为 n 的任务。 **贪婪：**总是选择最频繁的剩余任务。答案取决于最大频率以及有多少任务共享它。