用数量最少的箭引爆气球

力扣452-用数量最少的箭引爆气球 (opens new window)

解决思路：排序、贪心。

最直观的想法，有重叠的气球尽量采用一支箭引爆，这也是贪心的体现点。如果气球都是乱序的，不好确定如何才能使用一支箭引爆更多的气球。 因此首先按照气球的起始位置进行排序。（按结束位置排序也可，只是遍历方式有所不同）

之后遍历数组。为了确保一支箭能够引爆尽量多的气球，分为下面两种情况。

• 当前气球和起始位置大于上一个气球的结束位置。说明不重叠，箭数量+1。
• 若重叠。则需要更新可以重叠的边界。能够被一支箭引爆的气球的起始位置，一定要小于等于重叠气球中结束位置最小的气球的结束位置。

文字不好理解的话，可以从下面的模拟来看。

        标杆
[1.......6] 
   [2..........8] 
            [7.........12] 
                   [10.........16]

可以看到，第二个气球的起始位置小于第一个气球的结束位置，所以它们可以被一支箭引爆。 但是可能第二个气球的结束位置会出现小于第一个气球的结束位置的情况，所以需要更新结束位置的值。

var findMinArrowShots = function(points) {
    if(!points.length) return 0
    //按照起始位置将气球进行排序
    points = points.sort((a, b) => {
        return a[0] - b[0]
    })
    let result = 1
    //遍历
    for(let i = 1; i < points.length; i++) {
        //出现气球不重叠的情况，则需要的弓箭数量+1
        if(points[i][0] > points[i - 1][1]){
            result++
        }else{
            //如果重叠，则更新重叠的最大边界。即结束位置的最大值
            points[i][1] = Math.min(points[i - 1][1], points[i][1])
        }
    }
    return result
};