C++ easy to understand solution using sort starting point


  • 0
    M
    class Solution {
    public:
        int findMinArrowShots(vector<pair<int, int>>& points) {
            if(points.empty())
                return 0;
            //worst case needs the same number of arrows
            int cnt = points.size();
            
            //sort by the starting point
            sort(points.begin(), points.end(), [](const pair<int, int> &a, const pair<int, int> &b){return a.first<b.first;});
            for(int i=1;i<points.size();i++){
                if(points[i].first<=points[i-1].second){
                    //update the current point's ending by the smaller one so we can tell if the next's start will overlap or not
                    points[i].second = min(points[i-1].second, points[i].second);
                    cnt--;
                }
            }
            
            return cnt;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.