354. Russian Doll Envelopes (Hard)

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Example:

Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Solution 1: DP too slow!!! not recommended

Time Complexity: $$O(n^2+n)$$ 1213ms

这道题给了我们一堆大小不一的信封，让我们像套俄罗斯娃娃那样把这些信封都给套起来，这道题实际上是之前那道Longest Increasing Subsequence的具体应用，而且难度增加了，从一维变成了两维，但是万变不离其宗，解法还是一样的，首先来看DP的解法，这是一种brute force的解法，首先要给所有的信封按从小到大排序，首先根据宽度从小到大排，如果宽度相同，那么高度小的再前面，这是STL里面sort的默认排法，所以我们不用写其他的comparator，直接排就可以了，然后我们开始遍历，对于每一个信封，我们都遍历其前面所有的信封，如果当前信封的长和宽都比前面那个信封的大，那么我们更新dp数组，通过dp[i] = max(dp[i], dp[j] + 1)。然后我们每遍历完一个信封，都更新一下结果res，参见代码如下:

int maxEnvelopes(vector<pair<int, int>>& envelopes) {
    sort(envelopes.begin(), envelopes.end());
    int n = envelopes.size(), res = 0;
    // dp[i]: maximum number of envelopes you can put at position i
    // at beginning, dp[i] can put itself = 1
    vector<int> dp(n, 1); 

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (envelopes[i].first > envelopes[j].first 
                && envelopes[i].second > envelopes[j].second) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        res = max(res, dp[i]);
    }
    return res;
}

Solution 2: DP + Binary Search

Time Complexity: $$O(nlogn+n)$$

我们还可以使用二分查找法来优化速度，我们首先要做的还是给信封排序，但是这次排序和上面有些不同，信封的宽度还是从小到大排，但是宽度相等时，我们让高度大的在前面。那么现在问题就简化了成了找高度数字中的LIS，完全就和之前那道Longest Increasing Subsequence一样了，所以我们还是使用之前那题解法来做，参见代码如下：

version 1: 36ms

int maxEnvelopes(vector<pair<int, int>>& envelopes) {
    sort(envelopes.begin(), envelopes.end(), 
        [](pair<int,int>&a, pair<int,int>&b) { 
            if (a.first == b.first) return a.second > b.second; 
            return a.first < b.first;
        });

    // dp[i]: LIS by height at position i
    vector<int> dp; 

    for (auto& a: envelopes) {
        int left = 0, right = dp.size();
        while (left < right) {
            int mid = (left+right)/2;
            if (dp[mid] < a.second) left = mid+1;
            else right = mid;
        }
        if (right >= dp.size()) dp.push_back(a.second);
        else dp[right] = a.second;
    }
    return dp.size();
}

version 2: with lower_bound 43 ms

int maxEnvelopes(vector<pair<int, int>>& envelopes) {
    sort(envelopes.begin(), envelopes.end(), 
        [](pair<int,int>&a, pair<int,int>&b) { 
            if (a.first == b.first) return a.second > b.second; 
            return a.first < b.first;
        });

    // dp[i]: LIS by height at position i
    vector<int> dp; 

    for (auto& a: envelopes) {
        auto it = lower_bound(dp.begin(), dp.end(), a.second);
        if (it == dp.end()) dp.push_back(a.second);
        else *it = a.second;
    }
    return dp.size();
}