C++ solution in 8 lines


  • 1
    P
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        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> dp;
        for (auto e : envelopes) {
            auto it = lower_bound(dp.begin(), dp.end(), e.second);
            if (it == dp.end()) dp.push_back(e.second);
            else *it = 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.