Two simple and efficient solutions in C++


  • 1

    The basic DP solution first:

    class Solution {
    private:
        bool bigger(pair<int, int> a, pair<int, int> b)
        {
            return a.first>b.first && a.second>b.second;
        }
    public:
        int maxEnvelopes(vector<pair<int, int>>& envelopes) 
        {
            int size = envelopes.size();
            if(!size) return 0;
            sort(envelopes.begin(), envelopes.end(), less<pair<int, int>>());
            int maxRolls[size]{0}, maxRoll = 1;
            maxRolls[0] = 1;
            for(int i = 1; i < size; ++i)
            {
                maxRolls[i] = 1;
                for(int j = i-1; j >= 0; --j)
                    if(bigger(envelopes[i], envelopes[j]))
                        maxRolls[i] = max(maxRolls[i], maxRolls[j]+1);
                maxRoll = max(maxRoll, maxRolls[i]);
            }
            return maxRoll;
        }
    };
    

    Then the optimised O(nlogn) solution which is inspired by Longest Increasing Subsequence.

    class Solution {
    public:
        int maxEnvelopes(vector<pair<int, int>>& envelopes) 
        {
            int size = envelopes.size();
            sort(envelopes.begin(), envelopes.end(), [](pair<int, int> a, pair<int, int>b){
                return a.first<b.first || (a.first==b.first && a.second>b.second);
            });
            vector<int> collector;
            for(auto& pair: envelopes)
            {
                auto iter = lower_bound(collector.begin(), collector.end(), pair.second);
                if(iter == collector.end()) collector.push_back(pair.second);
                else if(*iter > pair.second) *iter = pair.second;
            }
            return collector.size();
        }
    };

Log in to reply
 

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