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

Offer 驾到，掘友接招！我正在参与2022春招系列活动-刷题打卡任务，点击查看活动详情。

用最少数量的箭引爆气球

题目地址： leetcode-cn.com/problems/mi…

题目描述：

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

一支弓箭可以沿着 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;
};
复制代码