Cinte's Leetcode Record
0%

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

Posted on Edited on In Disqus:
Symbols count in article: 1k Reading time ≈ 1 mins.

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

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
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.empty())
            return 0;
        sort(points.begin(), points.end(), [](auto& v1, auto& v2)
        {
            return v1[0] < v2[0];
        });
        int l = points[0][0], r= points[0][1];
        int ret = 1;
        for(int i = 1, n = points.size(); i < n; ++i)
        {
            int cl = points[i][0], cr = points[i][1];
            if((cl >= l && cl <= r) || (cr >=l && cr <= r))
            {
                l = max(l, cl);
                r = min(r, cr);
            }else
            {
                l = cl;
                r = cr;
                ++ret;
            }
        }
        return ret;
    }
};

另一种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.empty())
            return 0;
        sort(points.begin(), points.end(), [](auto& v1, auto& v2)
        {
            return v1[1] < v2[1]; // 这里与上面不同
        });
        int l = points[0][1];
        int ret = 1;
        for(int i = 1, n = points.size(); i < n; ++i)
        {
            if(points[i][0] > l) // 当弹出时候,假如后面还有能被他引爆的气球，他们这些气球必然可以被他的下一个箭引爆。
            // 例如[0, 5],[6, 7],[3, 8]
            {
                l = points[i][1];
                ++ret;
            }
        }
        return ret;
    }
};