Решение задачи 354. Russian Doll Envelopes
Представьте кучу бумажных конвертов разного размера. Конверты меньшего размера могут быть вложены внутрь конвертов большего размера, если и ширина, и высота меньшего конверта меньше ширины и высоты большего конверта. Нам предлагают каким-то способом выяснить какое наибольшее количество конвертов может быть последовательно вложено друг в друга. Признаюсь, до знакомства с задачей я был уверен, что Russian Doll это матрешка - существительное, обозначающее русскую игрушку. Однако авторы использовали для описания глагол to Russian Doll, что можно перевести как "заматрёшить". Применительно к задаче - нас просят узнать какое максимальное количество конвертов из всего данного объема возможно одновременно "заматрёшить".
Конверты представлены двумерным массивом envelopes, где envelopes[i] = [wi, hi]. w - ширина конверта, h - высота конверта. Конверты нельзя поворачивать, то есть ширину мы сравниваем с шириной, а высоту с высотой.
Есть довольно изящный алгоритм решения. Если отсортировать конверты по возрастанию ширины, а при одинаковой ширине - по убыванию высоты, то решением будет длина самой длинной восходящей подпоследовательности высот конвертов в отсортированном массиве. Если проанализировать сказанное, то становится ясно, что слева направо ширина конвертов будет увеличиваться, а при одинаковой ширине справа окажется конверт с меньшей или равной высотой. Так как мы будем искать строго восходящую подпоследовательность, то в ней не смогут оказаться конверты с равной высотой. Таким образом при равной ширине конверт с большей высоой окажется слева (см. условие нашей сортировки) и тоже не попадет в восходящую подпоследовательность. В ней смогут оказаться только конверты с последовательно возрастающей шириной и высотой. То есть, как раз те, которые нам подходят. Ну а так как последовательность будет максимальной длины, то ее длина и будет ответом на задачу.
Алгоритм поиска максимальной восходящей подпоследовательности я подробно рассмотрел в этой задаче.
Мой вариант решения доступен здесь.