Greedy, C++


  • 0
    S

    Use sort and lambda

    class Solution {
    public:
        
        int findMinArrowShots(vector<pair<int, int>>& points) {
            if(points.empty()) return 0;
            auto cmp = [](const pair<int,int> &p1,const pair<int,int> &p2) -> int {
                 if(p1.first==p2.first) 
                    return p1.second<p2.second;
                 return p1.first<p2.first;
            };
            sort(points.begin(),points.end(),cmp);
            int minVal = points[0].second;
            int arrows  =1;
            for(auto i = 1;i<points.size();++i) {
                if(points[i].first >minVal) {
                    minVal = points[i].second;
                    arrows++;
                }else {
                    minVal = min(minVal,points[i].second);
                }
            }
            return arrows;
        }
    };
    

Log in to reply
 

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