[LeetCode] 452. Minimum Number of Arrows to Burst Balloons

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:
Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

用最少数量的箭引爆气球。

有一些球形气球贴在一堵用 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

给一个数组，数组里面存的是类似 [left, right] 这样的区间，left 和 right 分别代表气球直径的起点和终点。求问如果要引爆所有的气球最少需要几只箭。

思路是贪心，类似会议室二。先对所有气球直径的终点排序，然后以第一个气球的终点为起点开始看，如果第二个气球的起点大于第一个气球的终点，就说明两个气球不重叠，则需要另一个箭；同时挪动 end 指针到第二个气球的终点。end 指针可以理解为箭指向的位置，如果下一个气球的起点跟箭不重叠，则需要下一个箭了。

复杂度

时间O(nlogn)
空间O(1)

代码

Java实现

class Solution {
    public int findMinArrowShots(int[][] points) {
        int len = points.length;
        // corner case
        if (points == null || len == 0) {
            return 0;
        }

        // normal case
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        int res = 1;
        int end = points[0][1];
        for (int i = 1; i < len; i++) {
            if (end < points[i][0]) {
                res++;
                end = points[i][1];
            }
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function (points) {
    // corner case
    if (points === null || points.length === 0) return 0;

    // normal case
    points = points.sort((a, b) => a[1] - b[1]);
    let res = 1;
    let firstEnd = points[0][1];
    for (let i = 1; i < points.length; i++) {
        if (points[i][0] > firstEnd) {
            res++;
            firstEnd = points[i][1];
        }
    }
    return res;
};