Ctrl K

Вырезать промежуток из отрезков

Средняя
Множество точек на прямой задано списком segments полуинтервалов [a, b) — точка x входит в отрезок, если a ≤ x < b. Отрезки отсортированы по возрастанию и не пересекаются. Из этого множества нужно вырезать полуинтервал gap = [x, y): убрать все точки, попадающие в него. Отрезок, который пробел задевает частично, укорачивается, а если пробел лежит строго внутри — распадается на два куска. Верните оставшееся множество в том же виде: отсортированный список непересекающихся полуинтервалов. Пустые куски в ответ не входят.
Пример 1
segments=[[-2, 1], [3, 8], [10, 12]], gap=[0, 5] → [[-2, 0], [5, 8], [10, 12]]

От [-2, 1) остаётся [-2, 0), от [3, 8) — [5, 8), а [10, 12) пробел не задевает.

Пример 2
segments=[[0, 9]], gap=[4, 6] → [[0, 4], [6, 9]]

Пробел попадает в середину отрезка и делит его на два куска.

Пример 3
segments=[[1, 2], [3, 4]], gap=[0, 10] → []
Ограничения
  • 1 ≤ len(segments) ≤ 10⁴
  • -10⁹ ≤ a < b ≤ 10⁹ для каждого отрезка
  • Отрезки отсортированы и не пересекаются: конец каждого ≤ начала следующего
  • gap = [x, y], -10⁹ ≤ x < y ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиДве доски и вода СредняяТройки с нулевой суммой СредняяСумма тройки ближе всего к цели СредняяЧетыре числа с заданной суммой СредняяСледующая расстановка по порядку Средняя
загружаем Python…
Вход
segments=[[-2, 1], [3, 8], [10, 12]], gap=[0, 5]
Ожидается
[[-2, 0], [5, 8], [10, 12]]

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