452. 用最少数量的箭引爆气球

2020-04-15

LeetCode

贪心

5 分钟读完 (大约 772 个字) 0次访问

leetcode 452. 用最少数量的箭引爆气球

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

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

示例:

输入: [[10,16], [2,8], [1,6], [7,12]]
输出: 2
解释: 对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。

方法：贪心

思路：本题主要是实现用最少的弓箭把所有的气球射爆，弓箭一次性可以射爆叠加处的所有气球，因此我们只需使用贪心找出最多的不重叠区间数即可，最多不重叠区间数即为所需的最小弓箭数，因为其他区间必然是与不重叠区间中的一个或者多个相重叠于一处的（其他区间必定会重叠于不重叠区间的开始或者结尾处），所以只需要射击不重叠区间处即可把所有气球射爆。

在每次不重叠区间的选择中，区间的结尾最为重要，选择的区间结尾越小，留给后面的区间的空间越大，那么后面能够选择的区间个数也就越大。按区间的结尾进行排序，每次选择结尾最小，并且和前一个区间不重叠的区间。

运行数据：执行用时：21 ms，内存消耗：47.4 MB

// LeetCode指定调用方法
public int findMinArrowShots(int[][] points) {
		
    // 如果区间为空，则直接返回0
    int count = points.length;
    if (count == 0) return 0;

    // 根据区间结尾排序
    Arrays.sort(points, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[1] - o2[1];
        }
    });

    // 选择结尾最小，并且和前一个区间不重叠的区间
    int number = 1;
    int index = 0;
    for (int i = 1; i < count; i++) {
        if (points[i][0] > points[index][1]) {
            number++;
            index = i;
        }
    }

    //返回不重叠区间数
    return number;
}