leetcode 354.
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. This problem is the same as tallest box problem. First solution is to build the directed graph. Edge indicates relationship between 2 envelopes. This takes O(n^2) time complexity.
Another great solution is from here. First, it sort the envelopes by ascending order of width. If 2 envelopes has same widths, order them by descending order of height. Because same widths envelope are not able to put together. After that, we find the longest subsequence of height array.
For example, if envelopes = [[1, 1], [1, 2], [2, 1], [2, 2]], then the sorted array should be [[1,2], [1, 1], [2, 2], [2, 1]]. The height array is [2, 1, 2, 1]. Then, the longest subsequence will be [1, 2]. So answer is length of it: 2.
The code to sort the array and find the longest subsequence are both very brilliant. I would like to directly put the code here:
public static int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
if (o1[0] == o2[0]) { // if width are same, then order in descending order of height
return o2[1] - o1[1];
}
else {
return o1[0] - o2[0]; // if width are different, order them normally
}
}
});
int[] rec = new int[envelopes.length];
int len = 0;
for (int[] envelope : envelopes) {
int pos = Arrays.binarySearch(rec, 0, len, envelope[1]);
// negative means didn't find the element. Then it points to first element which is greater than envelope[1]
if (pos < 0) {
pos = -pos - 1;
}
rec[pos] = envelope[1];
if (pos == len) {
len++;
}
}
return len;
}
Time complexity is O(NlogN).
Check my code on github: link