我们一起用最少的箭头引爆气球

二维空间中有许多球形气球。对于每个气球，提供的输入是气球直径在水平方向上的起点和终点坐标。既然是横的，纵坐标就无所谓了，知道起点终点横坐标就够了。起始坐标总是小于结束坐标。弓箭可以从x轴上的不同点完美地垂直射出。在坐标x处射箭，如果有一个气球的直径起点和终点在坐标xstart，xend，且满足xstart≤x≤xend，则气球会被引爆。可以射出的弓的数量没有限制。弓箭一旦射出，便可以无限前进。我们想找到引爆所有气球所需的最少弓箭数量。给定一个数组points，其中points[i]=[xstart,xend]，返回爆炸所有气球所必须射出的最少箭数。示例1：输入：points=[[10,16],[2,8],[1,6],[7,12]]输出：2解释：对于这个例子，x=6可以爆炸[2,8],[1,6]两个气球，x=11爆炸另外两个气球示例2：输入：points=[[1,2],[3,4],[5,6],[7,8]]输出：4示例3：输入：points=[[1,2],[2,3],[3,4],[4,5]]输出：2示例4：输入：points=[[1,2]]输出：1示例5：输入：points=[[2,3],[2,3]]输出：1提示：0<=points.length<=10^4points[i].length==2-2^31<=xstartpoints[i-1][1]){//气球i和气球i-1不相邻，注意这不是>=result++;//需要一个箭头}else{//ballooniandballooni-1nexttopoints[i][1]=min(points[i-1][1],points[i][1]);//更新重叠气球的最小右边界}}returnresult;}};时间复杂度O(nlogn)，因为有快排空间复杂度O(1)，可见代码并不复杂。注意事项注意题目说的：满足xstart≤x≤xend，则气球会被引爆。那么就是说两个气球可以一起射而不重叠，所以代码中的if(points[i][0]>points[i-1][1])不能>=来总结这道题的贪心思路是很简单直接，就是反复一起拍，但是我觉得这道题很难。就算想法再好，很多同学也很想模拟一下模拟放气球的过程，实时将气球从阵列中取出。这样写会很复杂。而且，找重复的气球，找重叠气球的最小右边界其实也是有代码技巧的。贪心问题有时就是这样。看起来很简单，思路也很直白，但是代码一旦写出来，感觉很复杂，很难下手。其实这里需要代码功底，那么如何练代码功底呢？本文转载自微信公众号“代码随想”，可通过以下二维码关注。转载本文请联系CodeCaprice公众号。