LeetCode（#452）：用最少数量的箭引爆气球

一、前言

本题为LeetCode第452题，是一道 贪心算法 相关的算法题，难度中等。

本题链接：#452. 用最少数量的箭引爆气球

二、题目

       在一个二维空间内，有许多球形的气球。对于每个气球，都提供其直径开始和结束的横坐标，且开始坐标总小于结束坐标。

       一支弓箭在不同点垂直于X轴射出，若射出时的坐标点位于某气球的开始和结束坐标之间，则该气球会被射爆，即射出坐标为x，气球开始和结束坐标分别为x s和x e，若x s ≤ x ≤ x e，则气球被射爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。求解使得所有气球全部被射爆，所需的弓箭的最小数量。

       提供一个数组 points，其中 points [i] = [xstart, xend]，返回射爆所有气球所必须射出的最小弓箭数。

示例1：

// x = 6，射爆 [2,8],[1,6] 两个气球， x = 11 射爆另外两个气球
Input: points = [[10,16], [2,8], [1,6], [7,12]]
Output: 2

示例2：

// x = 2，射爆 [1,2],[2,3] 两个气球， x = 4 射爆另外两个气球
Input: points = [[1,2], [2,3], [3,4], [4,5]]
Output: 2

三、思路

       这是一道求最优解的算法题，可以尝试使用贪心算法进行解题，使得射出一支箭可以射爆更多的气球。

       将气球按照结束坐标进行升序排序。射爆第一个气球（x1,x2），需要射出坐标位于[x1,x2]之间的箭，但为了能射爆更多结束坐标在后面的气球，该箭的射出坐标应该位于结束坐标x2。排除已经射爆的气球，重复刚才的步骤，直至所有气球被射爆，结束循环，即可求出弓箭的最少数量。

       贪心策略：优先考虑结束坐标在最左边的气球，位于该气球结束坐标的一箭，可射爆最多数量的气球。

示例： points = [[10,16], [2,8], [1,6], [7,12]]

1. 将数组按照结束坐标进行升序排序； points = [[1,6], [2,8], [7,12], [10,16]]

2. 考虑第一个气球 [1,6] ，射出x = 6的一箭，可射爆 [1,6] 和 [2,8] ;

3. 排除被射爆的气球，考虑剩余的第一个气球 [7,12]； points = [[7,12], [10,16]]

4. 射出x = 12的一箭，可射爆 [7,12] 和 [10,16]；

5. 所有气球被射爆，共射出2箭，因此最少数量为2。

四、Java代码

public class soultion {
    public int findMinArrowShots(int[][] points) {
        // 按结束坐标进行升序排序
        // Arrays.sort(points, (a, b) -> a[1] > b[1] ? 1 : -1);
        Arrays.sort(points, Comparator.comparingInt(o -> o[1]));

        int count = 1;
        int end = points[0][1];
        for(int i = 1; i < points.length; i++) {
            if( points[i][0] > end ) {
                count++;
                end = points[i][1];
            }
        }

        return count;
    }
}

五、补充

       上述代码中，按照结束坐标进行升序排序，第一种方法是用的Lambda表达式，一般为Arrays.sort(points, (a, b) -> a[1] - b[1]);，但int的取值范围为[ -2^31, 2^31 - 1]，假如a[1] = 2^31 - 1，b[1] = -2^31，则a[1] - b[1] 会超出int取值范围而报错，因此用Arrays.sort(points, (a, b) -> a[1] > b[1] ? 1 : -1);。

       第二种方法Arrays.sort(points, Comparator.comparingInt(o -> o[1]));，comparingInt()可接收一个方法，返回一个比较器Comparator。

LeetCode（#452）：用最少数量的箭引爆气球

原文：https://www.cnblogs.com/ziqin/p/14613865.html