n городов с номерами от 0 до n - 1. Изначально из каждого города i ведёт односторонняя дорога в город i + 1 (для всех 0 ≤ i < n - 1).
По очереди открывают скоростные трассы: shortcuts[i] = [u, v] — новая односторонняя дорога из города u в город v, где u < v (она может повторять уже существующую дорогу). Трассы никогда не перекрещиваются: не бывает двух трасс [a, b] и [c, d] с a < c < b < d. Две трассы либо вложены одна в другую, либо не пересекаются (общий конец допускается).
После открытия каждой трассы найдите наименьшее число дорог на пути из города 0 в город n - 1. Верните массив этих чисел в порядке открытия трасс.n=6, shortcuts=[[1, 4], [0, 1], [0, 4], [4, 5]] → [3, 3, 2, 2]
После трассы 1 → 4 путь 0 → 1 → 4 → 5 занимает три дороги. Трасса 0 → 1 повторяет уже существующую дорогу и ничего не меняет. С трассой 0 → 4 хватает двух дорог: 0 → 4 → 5. Трасса 4 → 5 тоже дублирует обычную дорогу.
n=5, shortcuts=[[0, 4], [1, 3]] → [1, 1]
Первая же трасса ведёт прямо из начала в конец, дальше ответ не меняется.
n=6, shortcuts=[[1, 4], [0, 1], [0, 4], [4, 5]]
[3, 3, 2, 2]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 15 тестов на сервере, включая скрытые.