C++ 46ms binary search


  • 0
    C
     class Solution {
        public:
            static bool myCompare(pair<int,int> p1, pair<int,int> p2) {
                return p1.first!=p2.first? p1.first<p2.first : p1.second>p2.second;
            }
            
            int binarySearch(vector<int>& dp, int target) {
                if(dp.size()==0)
                    return 0;
                int l = 0, r = dp.size()-1;
                while(l<r-1) {
                    int m = (l+r)>>1;
                    if(dp[m]>=target)
                        r = m;
                    else
                        l = m + 1;
                }
                if(dp[l]>=target)
                    return l;
                if(dp[r]>=target)
                    return r;
                return dp.size();
            }
            
            int maxEnvelopes(vector<pair<int, int>>& envelopes) {
                sort(envelopes.begin(),envelopes.end(),myCompare);
                vector<int> dp;
                for(auto e:envelopes) {
                    int idx = binarySearch(dp,e.second);
                    if(idx==dp.size())
                        dp.push_back(e.second);
                    else
                        dp[idx] = e.second;
                }
                return dp.size();
            }
        };

Log in to reply
 

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