Russian Doll Envelopes

1public int maxEnvelopes(int[][] envelopes) {
2    if (envelopes == null || envelopes.length == 0) return 0;
3
4    // Sort by width ascending, height descending
5    Arrays.sort(envelopes, (a, b) -> {
6        if (a[0] == b[0]) return b[1] - a[1];
7        return a[0] - b[0];
8    });
9
10    int[] tails = new int[envelopes.length];
11    int size = 0;
12
13    for (int[] envelope : envelopes) {
14        int num = envelope[1];
15        int left = 0, right = size;
16        while (left < right) {
17            int mid = left + (right - left) / 2;
18            if (tails[mid] < num) {
19                left = mid + 1;
20            } else {
21                right = mid;
22            }
23        }
24        tails[left] = num;
25        if (left == size) {
26            size++;
27        }
28    }
29    return size;
30}