Leetcode 354 Solution

This article provides solution to leetcode question 354 (russian-doll-envelopes)
Categories:
Tags:
Access this page by simply typing in "lcs 354" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/russian-doll-envelopes

Solution

class Solution {
public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        if (envelopes.size() == 0)
            return 0;

        sort(envelopes.begin(), envelopes.end(), [] (const pair<int, int>& p1, const pair<int, int>& p2)
        {
            if (p1.first < p2.first)
                return true;
            else if (p1.first == p2.first && p1.second > p2.second)
                return true;
            else
                return false;
        });

        vector<int> lis;
        int max_lis = 0;

        for (auto pair : envelopes)
        {
            int val = pair.second;
            int l = 0;
            int r = lis.size() - 1;

            while (l <= r)
            {
                int m = (l + r) / 2;

                if (lis[m] >= val)
                    r = m - 1;
                else
                    l = m + 1;
            }

            if (l == lis.size())
                lis.push_back(val);
            else
                lis[l] = val;

            max_lis = max(max_lis, (int)lis.size());
        }

        return max_lis;
    }
};