c++ greedy solution easy to understand


  • 0
    Q
    class Solution {
    public:
        int findMinArrowShots(vector<pair<int, int>>& points) {
            struct compare{
                bool operator()(pair<int, int> a, pair<int, int> b){
                    if(a.first < b.first || (a.first == b.first && a.second <= b.second))
                        return true;
                    else
                        return false;
                }
            };
            
            int len = points.size();
            if(len == 0)
                return 0;
            sort(points.begin(), points.end(), compare());
            int i = 1;
            int cnt = 1;
            int start = points[0].first, end = points[0].second;
            while(i<len){
                pair<int,int> tmp = points[i];
                if(tmp.first <= end){
                    start = tmp.first;
                    end = min(end, tmp.second);
                }
                else{
                    cnt++;
                    start = tmp.first;
                    end = tmp.second;
                }
                i++;
            }
            return cnt;
            
        }
    };
    

Log in to reply
 

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