Ctrl K

Свободные отрезки

Лёгкая
Номера мест в зале — целые числа от low до high включительно. Занятые места перечислены в массиве taken: он отсортирован по возрастанию, номера в нём не повторяются и все лежат в этих границах. Верните свободные места в виде как можно меньшего числа отрезков [a, b] (места с a по b включительно). Отрезки должны идти по возрастанию, не задевать ни одного занятого места и вместе покрывать все свободные.
Пример 1
taken=[3, 4, 9], low=1, high=12 → [[1, 2], [5, 8], [10, 12]]

Свободны 1–2, 5–8 и 10–12.

Пример 2
taken=[], low=-5, high=5 → [[-5, 5]]

Ничего не занято — весь диапазон одним отрезком.

Пример 3
taken=[6, 7, 8], low=6, high=8 → []

Занято всё, свободных отрезков нет.

Ограничения
  • -10⁹ ≤ low ≤ high ≤ 10⁹
  • 0 ≤ len(taken) ≤ 100
  • low ≤ taken[i] ≤ high
  • taken строго возрастает
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПара с заданной суммой ЛёгкаяСжать повторы в отсортированном массиве ЛёгкаяВыкинуть лишнее значение ЛёгкаяМесто на отсортированной полке ЛёгкаяПрибавить единицу к числу из цифр Лёгкая
загружаем Python…
Вход
taken=[3, 4, 9], low=1, high=12
Ожидается
[[1, 2], [5, 8], [10, 12]]

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