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

原题链接：452. 用最少数量的箭引爆气球

 

solution:
        贪心策略:将所有区间按右端点从小到大进行排序,每次选择区间的右端点进行射击。

 

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        int n = points.size();
        sort(points.begin(),points.end(),[](const vector<int> &a, const vector<int> &b){
            return a[1] < b[1];
        });
        int res = 1,ed = points[0][1];
        for(int i = 1;i < n;i++) {
            if(points[i][0] > ed) {
                res++;
                ed = points[i][1];
            }
        }

        return res;
    }
};