LeetCode_104_MinimumNumberOfArrowsToBurstBalloons

1. question: 用最少数量的箭引爆气球（中等）

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons

示例 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

2. answers

这道题最开始想的是，只要气球重叠，那么就可能减少箭数。因此，应该判断气球是否重叠，那么怎么判断重叠呢？为了方便，应该根据气球的左边界进行排序。这样，后面的气球的左边界小于等于前面气球的右边界，就重合了（因为排序后，肯定是大于等于前面气球的左边界）。

那么重合之后呢？再后面的气球应该怎么判断是否和前面的重合？我们知道，如果一箭三雕，那必然三个气球都在一定的区间内，也就是说，第三个气球一定是前两个气球重叠的区间内，这样才可能一箭三雕。

因此，排序后，只需要判断是否和上一个重合区间是否重合即可，此时需要保存上一个重合区间的右边界。为了方便，可设置上一个气球的右边界为该气球所在重合区间的右边界。

后续判断的时候，如果重合，那么就无需增加一支箭；如果不重合，那么就需要增加一支箭。

注意，这里有一个很容易想到的疑问，就是当前气球A、B重合了，那么怎么保证B是最优的重合呢？会不会和后续的CDE都重合呢？

首先，如果和CDE都重合，另外，如果A也和他们重合，显然通过上面的步骤是可以推断出来的。

如果A不和他们重合，那么最少需要两支箭，因此，无论B放在哪个重合区间里，都是无可厚非的。

参考了题解，代码如下所示：

public class Solution_0104_02 {

    public int findMinArrowShots(int[][] points) {

        // 对给定的气球排序，根据左边界从小到大
        Arrays.sort(points, Comparator.comparingInt(a -> a[0]));

        // 初始化箭数为1，即第一个气球的直径范围。
        int result = 1;

        for (int i = 1; i < points.length; i++) {

            // 重合，则更新上一个重叠区间的区间范围（右区间即可）
            if(points[i][0] <= points[i - 1][1])
                points[i][1] = Math.min(points[i - 1][1], points[i][1]);
            else
                result++;
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println();

//        int[][] points = {{10,16},{2,8},{1,6},{7,12}};
//        int[][] points = {{1,2},{3,4},{5,6},{7,8}};
        int[][] points = {{1,2},{2,3},{3,4},{4,5}};

        Solution_0104 s = new Solution_0104();

        System.out.println(s.findMinArrowShots(points));

    }
}

根据上面的分析，自己后来思考了一种方法，就是找尽可能小（直径）的独立气球，因为重叠的气球都是和这些独立气球共用一支箭的。这些独立气球就是所需的最少箭数。但是这样做是有问题的，如果一个独立气球A和其他BC两个气球都重叠，各占左右两部分，但是BC不重叠，显然这是需要两支箭的，本质上还是需要更新重叠空间。所以就又回到了上面的思路。

所以，核心是重叠区间的更新以及判断。

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。