Minimum Number Of Arrows To Burst Balloons

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

算法

要保证最少的弓箭数，我们可以采用如下贪心策略：
- 按区间的结束点升序排序：优先处理结束点较小的区间，这样可以最大化覆盖更多的区间
- 每次发射箭时，记录当前箭能够覆盖的结束点 r 。如果后续某个气球的开始点 x_start 大于当前箭的覆盖范围 r，则需要发射一支新的箭

将所有气球的直径区间按照结束点升序排序
初始化箭的数量 res 为 1，并将第一支箭的覆盖范围设为第一个区间的结束点
遍历排序后的区间：
- 如果当前区间的开始点大于箭的覆盖范围，说明需要一支新的箭来覆盖当前气球
- 更新箭的覆盖范围为当前区间的结束点

复杂度分析

排序的时间复杂度为 O(nlogn)，其中 n 是气球的数量；遍历区间的复杂度为 O(n)；总时间复杂度为 O(nlogn)
空间复杂度为 O(1)

C++ 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution
{
public:
    int findMinArrowShots(vector<vector<int>>& points)
    {
        // 如果没有气球，返回 0
        if (points.empty())
            return 0;

        // 按区间结束点升序排序
        std::sort(points.begin(), points.end(), [](std::vector<int> a, std::vector<int> b) {
            return a[1] < b[1];
        });

        // 初始化箭的数量和当前箭的覆盖范围
        int res = 1; // 至少需要一支箭
        int r = points[0][1]; // 第一支箭的覆盖范围

        // 遍历剩余的区间
        for (int i = 1; i < points.size(); ++i)
        {
            // 如果当前区间的起始点在当前箭的覆盖范围之外
            if (r < points[i][0])
            {
                ++res; // 增加一支箭
                r = points[i][1]; // 更新箭的覆盖范围
            }
        }

        return res;
    }
};

Python 代码

1
2
3
4
5
6
7
8
9


class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
      points.sort(key = lambda point: point[1])
      res, r = 1, points[0][1]
      for i in range(1, len(points)):
        if r < points[i][0]:
          r = points[i][1]
          res += 1
      return res

Go 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


import "sort"

func findMinArrowShots(points [][]int) int {
  sort.Slice(points, func(i, j int) bool {
    return points[i][1] < points[j][1]
  })
  res, r := 1, points[0][1]
  for i := 1; i < len(points); i += 1 {
    if r < points[i][0] {
      r = points[i][1]
      res += 1
    }
  }
  return res
}