Задача с собеседования в Google: Russian Doll Envelopes

Задача. Дан двумерный массив envelopes, где envelopes[i] = [wᵢ, hᵢ] — ширина и высота i-го конверта.
Один конверт может быть вложен в другой, если его ширина и высота строго меньше ширины и высоты другого конверта.

Требуется найти максимальное число конвертов, которые можно вложить друг в друга.

Например,
envelopes = [[5,4],[6,4],[6,7],[2,3]]

Output: 3.
Можно вложить максимум 3 конверта друг в друга: [2,3] => [5,4] => [6,7]

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1
По условию, конверты, одинаковые хотя бы по одному измерению, нельзя вкладывать друг в друга.

Ссылка на leetcode: https://leetcode.com/problems/russian-doll-envelopes/description/

Решение.
Решение разобрал тут: Задача с собеседования в Google: Russian Doll Envelopes

Код решения:

Вариант 1. Динамическое программирование.

public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, (a, b) -> {
        if (a[0] == b[0]) {
            return Integer.compare(a[1], b[1]);    
        }
        return Integer.compare(a[0], b[0]);
    });

    int[] dp = new int[envelopes.length];
    Arrays.fill(dp, 1);

    int result = 1;

    for (int i = 0; i < envelopes.length; i++) {
        for (int j = 0; j < i; j++) {
            if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        result = Math.max(result, dp[i]);
    }

    return result;
}

Вариант 2. Бинарный поиск.

public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, (a, b) -> {
        if (a[0] == b[0]) {
            return Integer.compare(b[1], a[1]);
        } else {
            return Integer.compare(a[0], b[0]);
        }
    });

    int[] tails = new int[envelopes.length];
    int size = 0;

    for (int i = 0; i < envelopes.length; i++) {
        int h = envelopes[i][1];

        int left = 0, right = size;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (tails[mid] < h) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        tails[left] = h;
        if (left == size) {
            size++;
        }
    }

    return size;
}