452. detonate the balloon with the minimum number of arrows

Original link ：452. Detonate the balloon with a minimum number of arrows

 

solution:
        Greedy strategy : Sort all intervals from small to large according to the right endpoint , Select the right end of the interval to shoot each time .

 

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;
    }
};