idea - sort w by asc first, but when w are the same, h do sort by desc, the focus on h find the LIS (leetcode 300)
when widths are the same, why height should do sort by desc?
sort + DP + binary search
class Solution {
public int maxEnvelopes(int[][] envelopes) {
// sort width first small to large, if width is the same, height pick larger one
Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int[] tails = new int[envelopes.length];
int res = 0;
for(int envelope[] : envelopes) {
int i = binarySearch(tails, res, envelope[1]); // for height to do the 300. Longest Increasing Subsequence
tails[i] = envelope[1];
if(res == i) res++;
}
return res;
}
private int binarySearch(int tails[], int res, int num) {
int i = 0, j = res;
while(i < j) {
int m = (i + j) / 2;
if(tails[m] < num) {
i = m + 1;
} else {
j = m;
}
}
return i;
}
}
```java
class Solution {
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
Arrays.sort(envelopes, (a, b) -> {
if (a[0] == b[0]) {
return b[1] - a[1];
}
return a[0] - b[0];
});
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
}
int result = 0;
for (int i = 0; i < n; i++) {
result = Math.max(result, dp[i]);
}
return result;
}
}
```
