Ctrl K

Свежая краска по дням

Сложная
Длинный забор представим как числовую прямую. Маляру выдали план на n дней: в день i нужно покрасить участок от jobs[i][0] до jobs[i][1]. Если красить одно место дважды, лягут пятна, поэтому маляр закрашивает только ту часть участка, которая ещё не покрашена в прошлые дни. Верните массив длины n, где i-й элемент — длина забора, впервые покрашенная в день i.
Пример 1
jobs=[[2, 6], [0, 3], [5, 9]] → [4, 2, 3]

В день 0 красим отрезок от 2 до 6 — длина 4. В день 1 из отрезка от 0 до 3 новый только кусок от 0 до 2 — длина 2. В день 2 кусок от 5 до 6 уже покрашен, новый — от 6 до 9, длина 3.

Пример 2
jobs=[[10, 20], [12, 15], [0, 30]] → [10, 0, 20]

Отрезок дня 1 целиком лежит внутри уже покрашенного, поэтому 0. В день 2 новые куски — от 0 до 10 и от 20 до 30.

Ограничения
  • 1 ≤ n = len(jobs) ≤ 10⁵
  • jobs[i] = [start, end], 0 ≤ start < end ≤ 5 · 10⁴
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиКонтур городской застройки СложнаяМеньшие справа СложнаяСуммы отрезков в заданной полосе СложнаяПары с крутым спадом СложнаяТёмный промежуток между фонарями Сложная
загружаем Python…
Вход
jobs=[[2, 6], [0, 3], [5, 9]]
Ожидается
[4, 2, 3]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 97 тестов на сервере, включая скрытые.