用最少数量的箭引爆气球

标签: 贪心 数组 排序

难度: Medium

有一些球形气球贴在一堵用 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 <= 105
  • points[i].length == 2
  • -231 <= xstart < xend <= 231 - 1

Submission

运行时间: 116 ms

内存: 48.4 MB

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0
        
        points.sort(key=lambda balloon: balloon[1])
        pos = points[0][1]
        ans = 1
        for balloon in points:
            if balloon[0] > pos:
                pos = balloon[1]
                ans += 1
        
        return ans

Explain

这个题解的思路是先按照气球结束坐标从小到大排序，然后从前往后遍历气球，用一支箭尽可能多地引爆气球。具体来说，初始化一个 pos 变量表示上一支箭的引爆位置，初始化为第一个气球的结束坐标。从第二个气球开始遍历，如果当前气球的开始坐标大于 pos，说明之前的箭无法引爆当前气球，需要增加一支箭，并更新 pos 为当前气球的结束坐标。遍历结束后，ans 即为最少需要的弓箭数。

时间复杂度: O(nlogn)

空间复杂度: O(1)

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0
        
        # 按照气球结束坐标从小到大排序
        points.sort(key=lambda balloon: balloon[1])
        # 初始化 pos 为第一个气球的结束坐标
        pos = points[0][1]
        # 初始化弓箭数为 1
        ans = 1
        # 遍历气球
        for balloon in points:
            # 如果当前气球的开始坐标大于 pos
            if balloon[0] > pos:
                # 则需要增加一支箭
                pos = balloon[1]
                ans += 1
        
        return ans

Explore

选择按气球的结束坐标进行排序是为了确保每次射箭时能尽可能多地覆盖后续的气球。这种排序方式可以帮助我们确定一个最迟的射箭点，即当前箭所能达到的最远气球的结束位置。这样可以保证在不失去引爆任何气球的前提下，用最少的箭覆盖最多的气球。如果按照开始坐标排序，我们可能会过早地放置箭，从而导致需要更多的箭来覆盖后面开始坐标较晚但结束坐标较早的气球。

排序气球的结束坐标的好处在于，它帮助我们确定射箭的最优位置。这种排序方式允许我们从当前射箭位置尽可能多地向后覆盖气球。在算法中，这种排序方法简化了决策过程：只要下一个气球的开始坐标在当前箭位置之后，就意味着需要新的箭。这样可以确保每次放置箭时，都是在目前可能的最迟点，从而尽可能地减少总箭数。

如果多个气球具有相同的结束坐标，它们可以被一支箭同时引爆。在算法中，这种情况下，这些气球的开始坐标可能不同，但只要有一个气球的开始坐标小于或等于当前的射箭位置（pos），所有这些气球都将被当前的箭覆盖。因此，这种情况不会增加所需的箭的数量，反而有助于减少总箭数，因为一箭可以同时引爆多个气球。

变量`pos`的更新策略是在确定必须引入新箭时才进行更新，因为这保证了每次更新都是必要的，并且每次更新都能尽可能多地覆盖未来的气球。此策略确保了每次放置的箭都是在当前可用的最迟射箭位置，从而尽可能减少总箭数。实际上，这已经是一个非常有效的策略，因为它是基于当前已知的最优解放置箭。其他策略，如频繁更新pos或在不同的条件下更新pos，通常不会减少箭的总数，反而可能增加复杂性和箭的数量。