leetcode-minimum-number-of-arrows-to-burst-balloons

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

　　有n个气球，每个气球在x轴的左右直径端点start和end已知，每次垂直发射一根针，如果针的位置处于某个球的直径范围内，那么气球破，求最少针数能扎破所有气球

题目分析

　　贪心法，先将所有气球按照end顺序排序，然后遍历，对于当前的气球end，如果下一气球start比当前end小于或者等于，那么下一气球不用单独扎破。否则end被更新，具体可以看下代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    static bool mysort(pair<int, int>& a, pair<int, int>& b){
        return a.second<b.second;
    }
    int findMinArrowShots(vector<pair<int, int>>& points) {
        int len = points.size();
        if (len == 0) {
            return 0;
        }
        sort(points.begin(), points.end(), mysort);
        int i = 1;
        int ans = 1;
        int v = points[0].second;
        for (i = 1; i < len; i++) {
            if (points[i].first <= v) {
               continue;
            }
            v = points[i].second;
            ans++;
        }
        return ans;
    }
};

　　时间复杂度 O(n * log(n) )