354. Russian Doll Envelopes

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?

簡而言之 就是為了對 h 做 LIS 找到最後的答案, 所以 w 一樣時, h 要做 desc 不然因為 LIS 是 asc 的 => 會錯

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

O(n^2) TLE

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