Russian Doll Envelopes

• Lintcode : 602 / Leetcode : 354
• Level : Hard

Problem

Give 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.
Find the maximum number of nested layers of envelopes.

Example
Example 1:

Input：[[5,4],[6,4],[6,7],[2,3]]
Output：3
Explanation：
the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
Example 2:

Input：[[4,5],[4,6],[6,7],[2,3],[1,1]]
Output：4
Explanation：
the maximum number of envelopes you can Russian doll is 4 ([1,1] => [2,3] => [4,5] / [4,6] => [6,7]).

Concept & Algorithm

筆記

Time Complexity & Space Complexity

First

time : O(n ^ 2)
space: O(n)

Second

time : O( < n ^ 2) (lower_bound will < O(n))
space: O(n)

Answer

/*
bool comparePairs(const pair<int,int>& a, const pair<int,int>& b){
    if (a.first < b.first) return true;
    if (a.first > b.first) return false;
    return a.second < b.second;
}

class Solution {
public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        int n = envelopes.size();
        if (n == 0) return 0;
        vector<int> dp(n, 1);
        int ans = 1;
        sort(envelopes.begin(), envelopes.end());
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }

};
*/
bool cmp(const pair<int,int>&x, const pair<int, int>&y) {
  return x.first != y.first ? x.first < y.first : x.second > y.second;
}

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

        sort(envelopes.begin(), envelopes.end(), cmp);
        vector<int> dp(n), height(n+1, INT_MAX);
        for (int i = 0; i < n; i++) {
            int k = lower_bound(height.begin(), height.end(), envelopes[i].second) - height.begin() ;
            dp[i] = k;
            height[k] = envelopes[i].second;
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = max(ans, dp[i]);
        }
        return ans + 1;
    }
};

tags: DP

​