什么是贪心？#

贪心算法（英语：greedy algorithm），是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。

可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。

贪心为什么能成功？#

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心算法之所以能在某些问题上得到最优解，是因为这些问题恰好具有两个关键性质：

1. 贪心选择性质 (Greedy Choice Property) 这听起来很专业，但意思很简单：你当前做出的局部最优选择，一定也包含在全局最优解里。换句话说，你的每一步“贪心”都不会让你走上歪路，它确实是通往最终正确答案的一步。你不必“后悔”之前的选择。

2. 最优子结构 (Optimal Substructure) 这个性质意味着：当你做出一个贪心选择后，剩下的问题，仍然是同类型的、规模更小的问题。 例如，在区间问题中，你选了一个区间后，剩下的问题就变成了“在更少的、符合条件的区间里，继续做选择”，问题的本质没有变。

我们怎么想出贪心策略？#

在做题时，我们一般遵循两步：

1. 猜：

   • 分析问题，寻找一种简单的、局部的最优衡量标准。
   • “怎样才算‘最好’？”是“结束最早”？“价值最高”？“耗时最短”？
   • 这个标准通常就是排序的依据。例如，看到“最多”、“最少”、“最大”等字眼，就可以思考是不是可以按某个属性排序来贪心。

2. 证：

   • 在脑海里简单地验证一下你的猜想。最常用的方法是反证法或交换论证。
   • 如果不按这个规则来，会怎么样？
   • 例如，在排队接水问题中，如果你想证明“时间短的优先”是正确的，就可以想：“如果有一个时间长的人排在了时间短的人前面，我把他们俩换一下位置，总等待时间是变长了还是变短了？” 如果交换后结果更优，就说明不符合你规则的情况肯定不是最优解。

1.1 区间不相交：选出最多不重叠的区间#

• 问题：给你很多区间，选出尽可能多的区间，让它们互不重叠。
• 贪心策略：按结束时间升序排序，优先选结束早的。
• 思路：为了给后面的区间留下尽可能多的空间，我们当然应该选一个能“最快完事”的区间。
• 实现步骤：
  1. 将所有区间按结束时间 r 从小到大排序。
  2. 初始化已选区间的结束时间 last_end = -∞。
  3. 遍历排序后的区间，如果当前区间的开始时间 l >= last_end，就选中它，并更新 last_end。

1.2 区间覆盖：用最少区间覆盖目标范围 [S, T]#

• 问题：用最少的区间，把目标范围 [S, T] 完全盖住。
• 贪心策略：从当前位置出发，选择一个能让你延伸到最远的区间。
• 思路：每一步都想“迈得最远”，这样总步数自然就少了。
• 实现步骤：
  1. 将所有区间按开始时间 l 从小到大排序。
  2. 设当前已覆盖的右边界为 cur（初始为 S）。
  3. 在所有能覆盖 cur 的区间里（即 l <= cur），找到那个右端点 r 最大的区间。
  4. 用这个最大的 r 更新 cur，重复此过程直到 cur >= T。

1.3 部分背包：物品可分割，求最大价值#

• 问题：背包容量有限，物品可以只拿一部分，怎么拿价值最高？
• 贪心策略：按性价比（单位重量的价值 $v/w$）降序拿。
• 思路：当然是先拿最“值钱”的东西，每一寸空间都要用在刀刃上。
• 实现步骤：
  1. 计算所有物品的性价比 v/w。
  2. 按性价比从高到低排序。
  3. 依次将物品装入背包，如果装不下整个，就装一部分直到背包装满。

1.4 排队接水：如何让总等待时间最短#

• 问题：$n$ 个人接水，用时不同，怎么排队大家等的总时间最少？
• 贪心策略：用时短的人排在前面 (Shortest Processing Time First)。
• 思路：让耗时久的人排在后面，可以减少他影响到的人数。排在前面的人，会影响到后面所有人的等待时间，所以这个位置要留给“贡献”等待时间最少的人。

1.5 纪念品分组：两人一组，限重，求最少组数#

• 问题：$n$ 件物品，每组最多两人，有重量上限，求最少组数。
• 贪心策略：排序后，让最重的和最轻的尝试配对。
• 思路：最重的人是最“难搞”的，我们优先处理他。如果连最轻的都不能和他配对，那别人更不行了。所以，要么他和最轻的配对，要么他自己一组。
• 实现步骤：
  1. 按重量排序。
  2. 用双指针 i 指向最轻，j 指向最重。
  3. 若 w[i] + w[j] <= limit，则配对成功，i 和 j 都移动。
  4. 否则，最重的 w[j] 只能单独一组，j 移动。

1.6 合并果子：每次合并两堆，求最小成本#

• 问题：每次合并两堆，成本是两堆重量和。求合并成一堆的最小总成本。
• 贪心策略：每次都合并当前最小的两堆。
• 思路：这和哈夫曼树的思想一样。重量越大的果子，越希望它被加的次数少。让小的数在底层被反复加，大的数在顶层最后加，总和才最小。
• 实现步骤：用一个小根堆（优先队列）来维护所有果子堆，每次取出两个最小的，合并后再放回去。

1.7 删数问题：删 $k$ 个数，使剩余的数最小#

• 问题：从一个数字字符串中删掉 $k$ 个字符，使结果最小。
• 贪心策略：维护一个单调递增的序列。
• 思路：要让数字小，就要让高位的数字尽可能小。从左到右遍历，如果发现当前数字比前面的数字小，就应该把前面的大数删掉，换上这个小数。
• 实现步骤：用栈。如果当前数字比栈顶小且还能删（$k>0$），就弹栈。最后，如果 $k$ 没用完，从尾部删。

1.8 货仓选址：找一个点，到所有点的距离和最小#

• 问题：数轴上很多点，找一个仓库位置，让所有点到仓库的距离总和最小。
• 贪心策略：选在中位数。
• 思路：中位数是平衡点。仓库位置偏左，右边的点会把它“往右拉”；偏右，左边的点会把它“往左拉”。只有在中位数，两边的“拉力”才均衡。