一、贪心算法之区间调度问题
运用贪心算法来做时间管理
贪心算法可以认为是动态规划算法的一个特例，相比动态规划，使用贪心算法需要满足更多的条件（贪心选择性质），但是效率比动态规划要高。
比如说一个算法问题使用暴力解法需要指数级时间，如果能使用动态规划消除重叠子问题，就可以降到多项式级别的时间，如果满足贪心选择性质，那么可以进一步降低时间复杂度，达到线性级别的。
什么是贪心选择性质呢，简单说就是：每一步都做出一个局部最优的选择，最终的结果就是全局最优。注意哦，这是一种特殊性质，其实只有一小部分问题拥有这个性质。
问题概述
贪心解法
正确的思路可以分为以下三步：
- 从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。
- 把所有与 x 区间相交的区间从区间集合 intvs 中删除。
- 重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。
应用举例
二、剪视频剪出贪心算法
思路分析
给定一个目标区间和若干小区间，如何裁剪和组合小区间拼凑出目标区间？
最少需要几个小区间？
- 前文多次说过，区间问题肯定按照区间的起点或者终点进行排序。因为排序之后更容易找到相邻区间之间的联系，如果是求最值的问题，可以使用贪心算法进行求解。
- 至于到底如何排序，这个就要因题而异了，我做这道题的思路是先按照起点升序排序，如果起点相同的话按照终点降序排序。
- 要用若干短视频凑出完成视频[0, T]，至少得有一个短视频的起点是 0。
- 这个很好理解，如果没有一个短视频是从 0 开始的，那么区间[0, T]肯定是凑不出来的。
- 如果有几个短视频的起点都相同，那么一定应该选择那个最长（终点最大）的视频。
- 这一条就是贪心的策略，因为题目让我们计算最少需要的短视频个数，如果起点相同，那肯定是越长越好，不要白不要，多出来了大不了剪辑掉嘛。
代码实现
实现上述思路需要我们用两个变量curEnd和nextEnd来进行：
复杂度
这段代码的时间复杂度是多少呢？虽然代码中有一个嵌套的 while 循环，但这个嵌套 while 循环的时间复杂度是O(N)。因为当i递增到n时循环就会结束，所以这段代码只会执行O(N)次。
但是别忘了我们对clips数组进行了一次排序，消耗了O(NlogN)的时间，所以本算法的总时间复杂度是O(NlogN)。
三、贪心思想：玩跳跃游戏
LeetCode 两道经典的贪心算法：跳跃游戏 I 和跳跃游戏 II。这两道题可以使用动态规划或者算法和贪心算法进行求解，通过实践，你就能更深刻地理解贪心和动规的区别和联系了。
- 贪心算法可以理解为一种特殊的动态规划问题，拥有一些更特殊的性质，可以进一步降低动态规划算法的时间复杂度。
跳跃游戏 I
有关动态规划的问题，大多是让你求最值的，比如最长子序列，最小编辑距离，最长公共子串。 那么贪心算法作为特殊的动态规划也一样，一般也是让你求最值。这题表面不是求最值，但可以改改：请问通过题目中的跳跃规则，最多能跳多远？如果能够越过最后一格，返回 true，否则返回 false。
- 所以说，这道题肯定可以用动态规划求解的。但是由于它比较简单，下一道题再用动态规划和贪心思路进行对比，现在直接上贪心的思路：每一步都计算一下从当前位置最远能够跳到哪里，然后和一个全局最优的最远位置farthest做对比，通过每一步的最优解，更新全局最优解，这就是贪心。
- 如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点
- 可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新
- 如果可以一直跳到最后，就成功了
跳跃游戏 II
现在的问题是：保证你一定可以跳到最后一格，请问你最少要跳多少次，才能跳过去？
动态规划的思路
- 自顶向下的递归 —— dp函数这么定义：
// 定义：从索引 p 跳到最后一格，至少需要 dp(nums, p) 个跳跃数
int dp(vector<int>& nums, int p);
- base case：当p超过最后一格时，不需要跳跃：
if (p >= nums.size() - 1) return 0;
- 备忘录消除 重叠子问题 ，取最小值为最终答案
- 该算法的时间复杂度是 递归深度 × 每次递归需要的时间复杂度，即 O(N^2)，在 LeetCode 上是无法通过所有用例的，会超时。
贪心的思路
贪心算法比动态规划多了一个性质：贪心选择性质。什么样的问题满足贪心选择性质。
- 刚才的动态规划思路：穷举所有子问题，然后取其中最小的作为结果。核心的代码中的for循环中陷入递归计算子问题，这就是动态规划时间复杂度高的原因。
真的需要「递归地」计算出每一个子问题的结果，然后求最值吗？只需判断哪一个选择最有「潜力」即可：
- 显然应该跳 2 步调到索引 2，因为nums[2]的可跳跃区域涵盖了索引区间[3..6]，比其他的都大。如果想求最少的跳跃次数，那么往索引 2 跳必然是最优的选择。
- 这就是贪心选择性质，我们不需要「递归地」计算出所有选择的具体结果然后比较求最值，而只需要做出那个最有「潜力」，看起来最优的选择即可。
- i和end标记了可以选择的跳跃步数，farthest标记了所有可选择跳跃步数[i..end]中能够跳到的最远距离，jumps记录了跳跃次数。
- 本算法的时间复杂度 O(N)，空间复杂度 O(1)，可以说是非常高效，动态规划都被吊起来打了。
- 贪心算法的实际应用还挺多，比如赫夫曼编码也是一个经典的贪心算法应用。更多时候运用贪心算法可能不是求最优解，而是求次优解以节约时间，比如经典的旅行商问题。
- 不过我们常见的贪心算法题目，就像本文的题目，大多一眼就能看出来，大不了就先用动态规划求解，如果动态规划都超时，说明该问题存在贪心选择性质无疑了。
四、当老司机学会了贪心算法
暴力解法
- 时间复杂度是 O(N^2)
暴力解法是否有重复计算的部分？是否可以抽象出「状态」，是否对同一个「状态」重复计算了多次？
- 变化的量就是「状态」:「起点」和「当前油箱的油量」，但这两个状态的组合有不下 O(N^2) 种，显然没有任何优化的空间。所以说这道题肯定不是通过简单的剪枝来优化暴力解法的效率，而是需要我们发现一些隐藏较深的规律，从而减少一些冗余的计算。
图像解法
把站点和与其相连的路看做一个整体，将gas[i] - cost[i]作为经过站点i的油量变化值：这样，题目描述的场景就被抽象成了一个环形数组，数组中的第i个元素就是gas[i] - cost[i]。
有了这个环形数组，我们需要判断这个环形数组中是否能够找到一个起点start，使得从这个起点开始的累加和一直大于等于 0。
如何判断是否存在这样一个起点start？又如何计算这个起点start的值呢？
- 将 0 作为起点肯定不行，因为sum在变化的过程中小于 0 了，不符合「累加和一直大于等于 0」的要求。
那如果 0 不能作为起点，谁可以作为起点呢？
- 看图说话，图像的最低点最有可能可以作为起点：如果把这个「最低点」作为起点，就是说将这个点作为坐标轴原点，就相当于把图像「最大限度」向上平移了。
不过，经过平移后图像一定全部在 x 轴以上吗？
- 不一定，因为还有无解的情况：如果sum(gas[…]) < sum(cost[…])，总油量小于总的消耗，那肯定是没办法环游所有站点的。
贪心解法
用贪心思路解决这道题的关键在于以下这个结论： 当选择站点i作为起点「恰好」无法走到 j，则i和j中间的任意站点k都不可能作为起点。
回想一下我们开头说的暴力解法是怎么做的？
如果我发现从i出发无法走到j，那么显然i不可能是起点。现在，我们发现了一个新规律，可以推导出什么？
- 如果我发现从i出发无法走到j，那么i以及i, j之间的所有站点都不可能作为起点。
看到冗余计算了吗？看到优化的点了吗？
这就是贪心思路的本质，如果找不到重复计算，那就通过问题中一些隐藏较深的规律，来减少冗余计算。
若有收获，就点个赞吧
0 人点赞
