Войти Регистрация
Алгоритмы

89. Матрёшка из коробок Авито Доставки

Сложная

На складе Авито Доставки лежат коробки, boxes[i] = [w, h] — ширина и высота в сантиметрах. Коробка A влезает в B, если у A и ширина, и высота строго меньше. Поворачивать коробки нельзя.

Верните наибольшее число коробок, которые можно вложить одна в другую цепочкой.

В работе: Самая длинная цепочка по двум критериям: версии с ростом двух метрик, вложенные интервалы, упаковка.

Пример 1

Ввод
boxes = [[5, 4], [6, 4], [6, 7], [2, 3]]
Вывод
3

[2, 3] → [5, 4] → [6, 7]. [6, 4] в [6, 7] не влезает: ширина равна.

Пример 2

Ввод
boxes = [[1, 1], [1, 1]]
Вывод
1

Одинаковые не вкладываются.

Ограничения

  • 1 ≤ длина boxes ≤ 10⁵
  • 1 ≤ w, h ≤ 10⁵
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def max_nested_boxes(boxes):
ДПНаибольшая возрастающая подпоследовательностьБинарный поискцельO(n log n)

Источник: наша задача на данных Авито. Условие пересказано своими словами.