leetcode 452.用最少数量的箭引爆气球 贪心法求解 （c++版本）_how to get only integer using fractional number in

题目描述

题目比较长，不是很容易理解。概括以下就是 气球有大小范围，气球与气球之间的范围可能会有重叠，那么在重叠处射箭则会引爆有重叠部分的所有气球 我们要计算的就是射爆所有的气球需要的最少的箭
那么按照我们的分析来看就是要将有重叠部分的气球一次性射爆才会有最小的射箭数，因此我们需要进行排序然后进行遍历
排序的方法很关键，因为是范围，因此需要用右边界来进行排序，左边界是不行的可能会导致下一次的判断出现问题

代码实现

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) 
    {
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size()==1)
        {
            return 1;
        }
        sort(points.begin(), points.end(), cmp);
        int conut = 1;
        int pre = points[0][1];
        for(int i = 1; i < points.size(); i++)
        {
            if(pre < points[i][0])
            {
                conut++;
                pre = points[i][1];
            }
        }
        return conut;
    }
};
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