题目链接

452. 用最少数量的箭引爆气球 - 力扣（LeetCode）

题目描述

points[i]==[x1,x2]表示第i个气球的左边界对应的x轴坐标和右边界对应的x轴坐标。

箭从x位置处垂直X轴射出，对于第i个气球，如果x1 < x < x2，那么气球i将会被射爆。

问返回引爆所有气球的最少弓箭数量。

输入输出样例

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

题目解释

求所有气球包含的最小区间个数

代码

个人实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 1) {
            return n;
        }
        // 按照右端点，从小到大排序
        sort(points.begin(), points.end(),
             [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; });
        int ans = 1; // 最少需要一支箭矢
        int end = points[0][1];
        for (int i = 1; i < n; i++) {
            if (points[i][0] > end) { // 这种情况说明左端点已经超出了区间
                ans++;
                end = points[i][1];
            }
        }
        return ans;
    }
};

官方实现

作者：力扣官方题解
链接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/solutions/494515/yong-zui-shao-shu-liang-de-jian-yin-bao-qi-qiu-1-2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) {
            return 0;
        }
        sort(points.begin(), points.end(), [](const vector<int>& u, const vector<int>& v) {
            return u[1] < v[1];
        });
        int pos = points[0][1];
        int ans = 1;
        for (const vector<int>& balloon: points) {
            if (balloon[0] > pos) {
                pos = balloon[1];
                ++ans;
            }
        }
        return ans;
    }
};