Description

Submission

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), 
            [](vector<int>& v1, vector<int>& v2) {
                if(v1[0] == v2[0]) return v1[1] > v2[1];
                return v1[0] < v2[0];
            }
        );

        vector<int> stk;
        for(auto& envelope: envelopes) {
            int x = envelope[1];

            if(stk.empty() || stk.back() < x) {
                stk.push_back(x);
            } else {
                auto it = lower_bound(stk.begin(), stk.end(), x);
                *it = x;
            }
        }

        return stk.size();
    }
};