Русские конверты
Hard
Каждый конверт задан парой
Найдите максимальную длину цепочки вложенных конвертов (каждый следующий строго вмещает предыдущий). Конверты с равной шириной или равной высотой друг в друга не вкладываются.
[ширина, высота]. Конверт A можно вложить в конверт B только если ширина A строго меньше ширины B и высота A строго меньше высоты B.Найдите максимальную длину цепочки вложенных конвертов (каждый следующий строго вмещает предыдущий). Конверты с равной шириной или равной высотой друг в друга не вкладываются.
Примеры:
Вход:
[[5, 4], [6, 4], [6, 7], [2, 3]]
Выход:
3
Объяснение: [[5,4],[6,4],[6,7],[2,3]]: цепочка [2,3] → [5,4] → [6,7] длины 3. Конверт [6,4] в эту цепочку не встаёт (с [5,4] высоты равны, с [6,7] ширины равны).
Вход:
[[1, 1], [1, 1], [1, 1]]
Выход:
1
Объяснение: [[1,1],[1,1],[1,1]]: все размеры равны, ни один нельзя вложить в другой → максимальная цепочка длины 1.
Вход:
[[1, 1]]
Выход:
1
Объяснение: [[1,1]]: один конверт → ответ 1.
Ограничения:
1 <= envelopes.length <= 10^5
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!