Ctrl K

Ближайшее общее окно

Средняя
Двое коллег хотят созвониться. У каждого есть список свободных промежутков: free_a и free_b, где [start, end] означает «свободен с момента start до момента end». Промежутки одного человека не пересекаются и не соприкасаются, но могут идти в любом порядке. Нужна встреча длиной ровно length: отрезок [s, s + length], целиком лежащий внутри свободного промежутка у каждого из двоих. Верните самый ранний такой отрезок в виде [s, s + length] или пустой список, если подходящего времени нет.
Пример 1
free_a=[[30, 45], [90, 150]], free_b=[[0, 40], [100, 120]], length=10 → [30, 40]

Обе свободны с 30 до 40 — ровно 10 минут, встреча [30, 40] подходит и раньше неё ничего нет.

Пример 2
free_a=[[30, 45], [90, 150]], free_b=[[0, 40], [100, 120]], length=15 → [100, 115]

Общее окно [30, 40] теперь коротко, следующее — [100, 120], встреча [100, 115].

Пример 3
free_a=[[5, 8]], free_b=[[8, 20]], length=1 → []

Окна соприкасаются лишь в момент 8 — общего отрезка длины 1 нет.

Ограничения
  • 1 ≤ len(free_a), len(free_b) ≤ 10⁴
  • 0 ≤ start < end ≤ 10⁹
  • 1 ≤ length ≤ 10⁶
  • промежутки одного человека не пересекаются и не соприкасаются
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиТройки с нулевой суммой СредняяСумма тройки ближе всего к цели СредняяЧетыре числа с заданной суммой СредняяФлажки трёх цветов СредняяСтудии для записи Средняя
загружаем Python…
Вход
free_a=[[30, 45], [90, 150]], free_b=[[0, 40], [100, 120]], length=10
Ожидается
[30, 40]

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