贪心策略是一种常见的算法思想，具体来说就是在解决一个问题的时候，总是做出当前最好的选择。也就是说，在不考虑整体最优的情况下，他做的是某种意义上的局部最优解。贪心算法不能得到所有问题的整体最优解。关键是贪心策略的选择。选择的贪心策略必须没有后遗症，即某个状态的前一个过程不会影响到以后的状态，只与当前状态相关，这和动态规划是一样的。LeetCode上有73个贪心策略问题。我们把它分成几种来解释。到目前为止，我们暂时只提供了覆盖问题。其他的可以期待我的新书或者以后的解题文章。覆盖，我们选择三个问题来解释。这三道题除了用贪心法，还可以尝试动态规划来求解。45.JumpingGameII,Difficult1024.VideoStitching,Moderate1326.TheMinimumNumberofTapstoIrrigateaGarden,difficultcoveringproblem的一大特征，我们可以将其抽象为给定的大区间I和n小区间numberaxisi[0],i[1],...,i[n-1]，求至少选择多少个小区间，让这些小区间的并集可以覆盖整个大区间。我们来看看这三个问题。45.JumpingGameII题目描述给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表您可以在该位置跳跃的最大长度。您的目标是使用最少的跳跃次数到达数组中的最后一个位置。示例：输入：[2,3,1,1,4]输出：2解释：到达最后一个位置的最小跳数为2。从索引0跳到索引1，跳1步，然后跳3步到达数组的最后一个位置。解释：假设你总能到达数组的最后一个位置。贪心策略思维就是在可跳范围内，每次选择一个能跳得更远的位置。既然题目保证你总能到达数组的最后一个位置，那么这个算法就完成了。如下图，起始位置为2，可跳跃范围为橙色。然后跳到3的位置，因为3可以跳得更远。如下图，当前位置是3，可以跳跃的范围是橙色的，而且因为4可以跳的更远，所以下次会跳到4的位置。在写代码的时候，我们用end来表示当前的跳跃边界。对于上图第一张橙色的1，第二张图中的橙色4，我们在遍历数组的时候，到达边界的时候会更新新的边界。图片来自https://leetcode-cn.com/u/win...代码代码支持：Python3Python3代码：class解决方法：defjump(self,nums:List[int])->int:n,cnt,furthest,end=len(nums),0,0,0foriinrange(n-1):furthest=max(furthest,nums[i]+i)如果i==end:cnt+=1end=furthest返回cnt复杂度分析时间复杂度：$O(N)$。空间复杂度：$O(1)$。1024.视频拼接主题描述你将获得一系列来自体育赛事的视频剪辑，持续时间为T秒。这些片段可能重叠并且长度可能不同。视频剪辑clips[i]全部由间隔表示：从clipsi开始到clipsi结束。我们甚至可以自由编辑这些片段，例如可以将片段[0,7]切割成[0,1]+[1,3]+[3,7]三部分。我们需要重新剪辑这些剪辑，将剪辑后的内容拼接成一个剪辑([0,T])，覆盖整个运动过程。返回所需片段的最小数量，如果任务无法完成，则返回-1。示例1：输入：clips=[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]],T=10输出：3解释：我们选择三个段[0,2]、[8,10]、[1,9]。然后，重新制作匹配段如下：[1,9]被重新切割为[1,2]+[2,8]+[8,9]。现在我们手上有[0,2]+[2,8]+[8,10]，这些覆盖了整个游戏[0,10]。示例2：输入：clips=[[0,1],[1,2]],T=5输出：-1解释：我们不能只用[0,1]和[0,2]覆盖[0,5]】整个过程。示例3：输入：clips=[[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6],9]],T=9输出：3解释：我们取片段[0,4]、[4,7]和[6,9]。示例4：输入：clips=[[0,4],[2,8]],T=5输出：2解释：注意，您可以在游戏结束时间之后录制视频。Tips:1<=clips.length<=1000<=clipsi,clipsi<=1000<=T<=100Idea贪心策略，我们选择满足条件的最大值。与上面不同的是，这次我们需要手动排序。事实上，贪心策略往往伴随着排序。我们按照clip[0]从小到大排序。如图：1不允许，所以有故障；2是可能的；3不是，因为我们当前片段的开始和结束时间分别是T之前的s和e。上一个片段的结束时间是t1，上一个片段的结束时间是t2。那么这种情况下t1其实是不需要的，因为t2完全可以覆盖：那么需要什么样的t1呢？如图：从代码上来说，就是s>t2andt2<=t1Code代码支持：Python3Python3Code:class解决方案：defvideoStitching(self,clips:List[List[int]],T:int)->int:#t1表示上一个所选剪辑的结束时间#t2表示上一个所选剪辑的结束时间t2,t1,cnt=-1,0,0clips.sort(key=lambdaa:a[0])fors,einclips:#s>t1确定不可接受，t1>=T已经okifs>t1ort1>=T:breakifs>t2andt2<=t1:cnt+=1t2=t1t1=max(t1,e)returncntift1>=Telse-1复杂度分析时间复杂度：由于使用排序（假设基于比较的排序），时间复杂度为$O(NlogN)$。空间复杂度：$O(1)$。1326.灌溉花园的最少水龙头数问题描述在x轴上有一个一维花园。花园的长度为n，从点0开始，到点n结束。花园中共有n+1个水龙头，位于[0,1,...,n]处。给定一个整数n和一个长度为n+1的整数数组ranges，其中ranges[i]（下标从0开始）表示：如果打开i点的水龙头，则可灌溉的面积为[i-ranges[i],i+范围[i]]。请归还能灌溉整个花园的最少数量的水龙头。如果花园里总是有不能灌溉的地方，请返回-1。示例1：输入：n=5,ranges=[3,4,1,1,0,0]输出：1解释：点0的水龙头可以灌溉范围[-3,3]点1的水龙头可以灌溉区间[-3,5]第2点的水龙头可以灌溉区间[1,3]第3点的水龙头区间[2,4]第3点的水龙头可以灌溉区间[4,4]水龙头可以灌溉区间[5,5]，只需要在点1打开水龙头就可以灌溉整个花园[0,5]。示例2：输入：n=3,ranges=[0,0,0,0]输出：-1解释：即使打开所有水龙头也无法灌溉整个花园。示例3：输入：n=7，范围=[1,2,1,0,2,1,0,1]输出：3示例4：输入：n=8，范围=[4,0,0,0,0,0,0,0,4]输出：2示例5：输入：n=8，范围=[4,0,0,0,4,0,0,0,4]输出：1提示：1<=n<=10^4ranges.length==n+10<=ranges[i]<=100Idea贪心策略，我们尝试找到能覆盖最远（右边）位置的tap，记录它覆盖的土地在最右边。我们使用furthest[i]来记录每次点击i可以覆盖的最右边的土地。一共有n+1个水龙头，我们遍历n+1次。每次我们计算水龙头的左右边界，[i-ranges[i],i+ranges[i]]我们更新左右边界范围内最远的水龙头，最后从land开始0到地n，记录水龙头的个数代码支持：Python3Python3代码：class解决方法：defminTaps(self,n:int,ranges:List[int])->int:furthest,cnt,cur=[0]*n,0,0foriinrange(n+1):l=max(0,i-ranges[i])r=min(n,i+ranges[i])forjinrange(l,r):furthest[j]=max(furthest[j],r)whilecur
