C++ solution (using best practices) nlogn with explanations


  • 1
    G
    class Solution {
    public:
        int maxEnvelopes(vector<pair<int, int>>& envelopes) 
        {
            //
            // Sort pairs by decreasing height. If height is equal, sort by increasing width.
            //
            
            sort(envelopes.begin(),envelopes.end(),[](const pair<int,int> &p1, const pair<int,int> &p2)->bool
            {
                return (p1.second < p2.second || (p1.second == p2.second && p1.first > p2.first));
            });
            
            vector<pair<int,int> > Res;
            
            for(auto &P : envelopes)
            {
                //
                // binary search for the pair that has width >= to the current pair
                //
    
                auto lb = lower_bound(Res.begin(),Res.end(),P,[](const pair<int,int> &P1, const pair<int,int> &P2)->bool
                {
                    return P1.first < P2.first;
                });
                
                //
                // no such pair exists - just insert it to result
                //
                
                if(lb == Res.end())
                {
                    Res.push_back(P);
                }
                else
                {
                    //
                    // we found a pair which has a width >= than P, replace it with P.
                    //
                    
                    *lb = P;
                }
            }
            
            return (Res.size());
        }
    };

Log in to reply
 

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