贪心算法：核心思想与解题模板
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好/最优（即最有利）的选择，从而希望导致结果是全局最好/最优的算法策略。
核心哲学
“活在当下，目光短浅。”
与动态规划（DP）的”顾全大局”不同，贪心算法不计算所有路径的组合，它只看眼前。
它能成功的唯一条件：
局部最优解 一定能推导出 全局最优解。
如果不满足这个条件，贪心就会走进死胡同。
贪心算法的解题三部曲
1. 确定贪心策略 (The Greedy Strategy)
这是最难的一步。通常需要通过排序来体现策略。
常见的排序维度：
- 按结束时间（资源释放最快）：如活动安排问题。
- 按价值/成本（收益最大或代价最小）：如霍夫曼编码。
- 按覆盖范围（收益最广）：如区间覆盖问题。
2. 验证策略 (Exchange Argument)
替换法证明：
假设存在一个最优解 ，而你的贪心策略产生了解 。
如果 和 不同，我们尝试把 中的第一个选择替换为 的选择。
如果替换后，解依然合法（不冲突），且剩下的空间/资源比 更多（或相等），那么我们就证明了 至少和 一样好。
如此递归，证明贪心策略永远是最优的。
3. 实现代码
- 排序
- 遍历 + 状态更新
- O(n) 或 O(n log n) 复杂度
经典示例：不重叠区间
题目：7. Maximum Number of Non-Overlapping Intervals
1. 策略选择
我们的目标是数量最大化。
要让数量多，就必须让每个区间占用的资源尽可能少，也就是结束得尽可能早，以便给后面的区间留出空间。
策略：按结束时间升序排序。
2. 核心逻辑：为什么按结束时间排是对的？
这是贪心算法的精髓——“资源尽早释放”。
想象时间轴是一条直线，我们要往里塞尽可能多的木块。
- 选结束最早的区间，意味着剩下的可用时间最长。
- 这不仅是为了当下的收益，更是为了给未来保留最多的可能性。
反证（为什么不按开始时间排）：
假设有一场会议 [1, 100]，它开始得最早（1点就开始），但它是个“时间黑洞”，一直持续到100点。
如果你按“开始时间”贪心，就会选它。结果后面所有 [2, 3], [4, 5] 等短会议全被它挡住了。
结论：开始早不代表“占用少”，结束早才代表“让出资源”。
3. 举一反三：贪心何时失效？
如果题目条件稍作修改，贪心就会失效，需要切换到动态规划 (DP)：
-
加权区间调度 (Weighted Interval Scheduling)： 如果每个会议的价值（权重）不同（比如有的会赚10块，有的赚1000块）。 此时单纯追求“数量最多”或“结束最早”就不够了，可能需要选那个少但值钱的会议。此时必须用 DP。
-
区间覆盖： 目标是“用最少的区间覆盖指定范围”。 策略变为：每次选能覆盖当前起点，且结束最远（覆盖范围最大）的区间。
总结
遇到贪心题，先问自己三个问题：
- 我要优化的指标是什么？（数量？价值？长度？）
- 做什么选择能最大化未来的可能性？
- 这个选择会不会像“时间黑洞”一样，堵死后续的路？
想清楚这三点，再动笔写代码。