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

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

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

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

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

• 示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

• 示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

• 示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

• 提示：

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

思路

要解决这个问题，我们可以使用贪心算法。我们可以先将气球按照结束坐标进行排序，然后依次选择每个气球的结束坐标作为射箭点，并移除所有被这一箭引爆的气球，直到所有气球都被引爆为止。

1. 排序：首先我们将气球按照结束坐标进行排序。这样可以保证每次选择的箭可以尽可能地引爆尽可能多的气球。
2. 初始化箭的数量和位置：我们初始化箭的数量为 1，并将第一支箭的位置设置为第一个气球的结束坐标。
3. 遍历气球列表：从第二个气球开始，检查当前气球的起始坐标是否大于箭的位置。如果是，则说明当前箭无法引爆这个气球，因此需要增加一支新的箭，并更新箭的位置为当前气球的结束坐标。
4. 返回箭的数量：最后返回箭的数量。

• 时间复杂度:O(nlog₂n)
• 空间复杂度:O(1)

代码

public int findMinArrowShots(int[][] points) {
    int arraws = 1;
    // 按照气球的结束坐标对气球进行排序
    Arrays.sort(points, Comparator.comparingInt(a -> a[1]));
    // 初始化箭的数量为 1，第一支箭射在第一个气球的结束坐标
    int arrowPos = points[0][1];
    for (int i = 1; i < points.length; i++) {
        // 如果当前气球的起始坐标大于箭的坐标，说明需要一支新的箭
        if (arrowPos < points[i][0]) {
            arrowPos = points[i][1];
            arraws += 1;
        }
    }
    return arraws;
}