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;
    }
};