C++ solution Time:O(n*log(n))


  • 0
    K
    class Solution {
    public:
        int findMinArrowShots(vector<pair<int, int>>& points) {
            if(points.empty()) return 0;
            //n*log(n)
            sort(points.begin(),points.end(),cmp);
            int arrows=1;
            pair<int,int> p=points[0];
            for(auto &pt:points)
            {
                if(pt.first>p.second)
                {
                    p=pt;
                    arrows++;
                }
                else
                {
                    p.first=pt.first;
                    p.second=min(p.second,pt.second);
                }
            }
            return arrows;
        }
        static bool cmp(pair<int,int> &a,pair<int,int> &b)
        {
            return a.first<b.first||(a.first==b.first&&a.second<b.second);
        }
    };

Log in to reply
 

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