【LeetCode】452. Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球（Medium）（JAVA）

2022-07-24 22:43:21

【LeetCode】452. Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球（Medium）（JAVA）

题目地址: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

题目描述：

There are some 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. The start is always smaller than the end.

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 traveling up infinitely.

Given an array points where points[i] = [xstart, xend], return the minimum number of arrows that must be shot to burst all balloons.

Example 1:

Input: points = [[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).

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4

Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2

Example 4:

Input: points = [[1,2]]
Output: 1

Example 5:

Input: points = [[2,3],[2,3]]
Output: 1

Constraints:

0 <= points.length <= 10^4
points[i].length == 2
-2^31 <= xstart < xend <= 2^31 - 1

题目大意

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

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

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

解题方法

先对 points 二维数组进行排序
从头开始，判断射出的第一支箭在什么地方
为了射出尽可能少的箭，当然应该在重合的最后一个地方：从第一个数组的开始，然后往后遍历找到 points[i][1] 最小的记录下为 max，如果下一个 points[i][0] 比 max 小就结束，前面应该射一箭了
note: -2^31 <= xstart < xend <= 2^31 - 1, 在排序的时候不能采用 a[0] - b[0] 的运算，int 会超限

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length <= 1) return points.length;
        Arrays.sort(points, (a, b) -> {
            if (a[0] == b[0]) {
                if (a[1] == b[1]) return 0;
                if (a[1] < b[1]) return -1;
                return 1;
            } else if (a[0] < b[0]) {
                return -1;
            }
            return 1;
        });
        int next = 0;
        int res = 0;
        do {
            next = nextIndex(points, next);
            res++;
        } while (next < points.length);
        return res;
    }

    public int nextIndex(int[][] points, int start) {
        if (start >= points.length) return start;
        int max = points[start][1];
        for (int i = start + 1; i < points.length; i++) {
            if (points[i][0] > max) return i;
            max = Math.min(max, points[i][1]);
        }
        return points.length;
    }
}

执行耗时:21 ms,击败了76.19% 的Java用户
内存消耗:46 MB,击败了83.75% 的Java用户

欢迎关注我的公众号，LeetCode 每日一题更新

码农公寓