贪心算法：用最少数量的箭引爆气球 🎈

用最少数量的箭引爆气球

题目地址： https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/

题目描述：

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

示例

输入：points = [[10,16],[2,8],[1,6],[7,12]]输出：2解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

输入： points = [[1,2],[3,4],[5,6],[7,8]]输出： 4

输入： points = [[1,2],[2,3],[3,4],[4,5]]输出： 2

题目分析

本题的难度并不算高，在看到题目和示例后，最后自己画一个图来看，这样能够比较直观的看到。

在[[10,16],[2,8],[1,6],[7,12]]的例子中，气球的位置大致就是这些水平线，箭头就是弓箭射出的位置，可以进行不断的切换。

但是如果每个范围都不断去测试弓箭射出引爆气球，数量会非常大。所以这里需要求极值，将气球数组按照右边界从大到小进行重新排序，然后以第一个气球的右边界为坐标射出弓箭（必然会引爆至少 1 个气球）。然后对气球数组进行遍历，把此坐标能引爆的气球从数组中排除，然后以当前数组第一个气球右边界重新射箭，这样重复循环到数组没有气球。

• 第一箭射穿的气球

• 第二箭射穿的气球

• 所有气球都被引爆

代码

用 while 进行循环，如果当前数组长度小于等于 0，结束循环，每次射箭位置都是当前数组第一个值的右边界，并且射箭次数+1。数组通过filter进行过滤操作，将还存在的气球组成的新数组覆盖掉当前气球数组。

var findMinArrowShots = function(points) {    // 将数组按最右边界进行排序    points.sort((a, b)=>{        return a[1] - b[1];    })    let attackCount = 0, attackPos = -1;    while(points.length > 0) {        // 射箭位置        attackPos = points[0][1];        attackCount++;        points = points.filter((item)=>{            if(attackPos >= item[0] && attackPos <= item[1]) {                return false;            } else {                return true            }        })    }    return attackCount;};