题目描述

解题思路

局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。
为了让气球尽可能的重叠，需要对数组进行排序。
那么按照气球起始位置排序，还是按照气球终止位置排序呢？
其实都可以！只不过对应的遍历顺序不同，我就按照气球的起始位置排序了。
既然按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。
从前向后遍历遇到重叠的气球了怎么办？
如果气球重叠了，重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。
以题目示例： [[10,16],[2,8],[1,6],[7,12]]为例，如图：（方便起见，已经排序）

可以看见气球1和气球2重叠，那么可以使用一根弓箭来射，而气球三的左边区间已经大于气球一的右边区间，所以需要一根弓箭来射。

public int findMinArrowShots(int[][] points) {
    if (points.length == 0) return 0;
    // Arrays.sort(points, (o1, o2) -> o1[0] - o2[0]); // 不能使用，存在负数
    // 这是因为差值过大而产生溢出。sort的时候不要用a-b来比较，要用Integer.compare(a, b)!!!
    Arrays.sort(points, (o1, o2) -> Integer.compare(o1[0], o2[0])); // 按照左边界进行排序
    int result = 1; // points不为空，至少需要一次
    for (int i = 1; i < points.length; i++) {
        if (points[i][0] > points[i - 1][1]) {  // 气球i和气球i-1不挨着
            result++;   // 需要一支弓箭
        } else {    // 气球i和气球i-1挨着
            // 更新重叠气球的最小右边界
            points[i][1] = Math.min(points[i - 1][1], points[i][1]);
        }
    }
    return result;
}