一、题目内容 中等

有一些球形气球贴在一堵用 XY 平面表示的墙面上。
墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

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

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

示例1：

输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2 解释：气球可以用2支箭来爆破: -在x = 6处射出箭，击破气球[2,8]和[1,6]。 -在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例2：

输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4 解释：每个气球需要射出一支箭，总共需要4支箭。

示例3：

输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2 解释：气球可以用2支箭来爆破:

  • 在x = 2处发射箭，击破气球[1,2]和[2,3]。
  • 在x = 4处射出箭，击破气球[3,4]和[4,5]。

提示：

  • 1 <= points.length <= 105
  • points[i].length == 2
  • -231 <= xstart < xend <= 231 - 1

    二、解题思路

    如何使用最少的弓箭呢？
    直觉上来看，貌似只射重叠最多的气球，用的弓箭一定最少，那么有没有当前重叠了三个气球，我射两个，留下一个和后面的一起射这样弓箭用的更少的情况呢？
    尝试一下举反例，发现没有这种情况。

那么就试一试贪心吧！局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。

算法确定下来了，那么如何模拟气球射爆的过程呢？是在数组中移除元素还是做标记呢？
如果真实的模拟射气球的过程，应该射一个，气球数组就 remove 一个元素，这样最直观，毕竟气球被射了。
但仔细思考一下就发现：如果把气球排序之后，从前到后遍历气球，被射过的气球仅仅跳过就行了，没有必要让气球数组 remove 气球，只要记录一下箭的数量就可以了。

为了让气球尽可能的重叠，需要对数组进行排序。
那么按照气球起始位置排序，还是按照气球终止位置排序呢？
其实都可以！只不过对应的遍历顺序不同，我就按照气球的起始位置排序了。
既然按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。
从前向后遍历遇到重叠的气球了怎么办？
如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。 :::info 遇到重叠的气球，需要把气球的边界缩小，也就是说，i 和 i - 1，要将 i 的右边界缩小 ::: image.png

三、具体代码

  1. /**
  2.  * @param {number[][]} points
  3.  * @return {number}
  4.  */
  5. var findMinArrowShots = function (points) {
  6.   if (points.length === 1) return 1
  7.   points.sort((a, b) => a[0] - b[0])
  8.   let result = 1 // 箭的数量
  9.   for (let i = 1, len = points.length; i < len; i++) {
  10.     if (points[i][0] - points[i - 1][1] > 0) result++
  11.     else points[i][1] = Math.min(points[i][1], points[i - 1][1])
  12.   }
  13.   return result
  14. };

四、其他解法