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;
}
};
