Ctrl K

Непокрашенные участки забора

Средняя
Забор состоит из length досок, пронумерованных от 0 до length - 1. Маляры прошлись по нему несколько раз: каждый элемент coats — пара [from, to], означающая, что покрашены все доски с from по to включительно. Полосы могут перекрываться и идти в любом порядке. Найдите все непокрашенные участки: каждый участок — это максимальный непрерывный отрезок досок без краски, который нельзя продлить ни влево, ни вправо. Верните их как пары [first, last], отсортированные по возрастанию first. Если голых досок нет, верните пустой список.
Пример 1
length=12, coats=[[2, 4], [7, 9], [3, 5]] → [[0, 1], [6, 6], [10, 11]]

Покрашены доски 2–5 и 7–9. Голыми остаются 0–1, 6 и 10–11.

Пример 2
length=4, coats=[[0, 1], [2, 3]] → []

Две полосы вместе закрывают весь забор — непокрашенных досок нет.

Пример 3
length=5, coats=[] → [[0, 4]]
Ограничения
  • 1 ≤ length ≤ 10⁹
  • 0 ≤ len(coats) ≤ 10⁶
  • 0 ≤ from ≤ to ≤ length − 1
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиТройки с нулевой суммой СредняяСумма тройки ближе всего к цели СредняяЧетыре числа с заданной суммой СредняяРазличные перестановки с повторами СредняяРазложить анаграммы по группам Средняя
загружаем Python…
Вход
length=12, coats=[[2, 4], [7, 9], [3, 5]]
Ожидается
[[0, 1], [6, 6], [10, 11]]

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