Войти Регистрация
Алгоритмы

124. Окна для встречи, когда свободен кворум

Сложная

busy[i] — встречи i-го сотрудника Т-Банка, пары [start, end] в минутах, конец не включается. Встречи одного человека могут пересекаться и идти в любом порядке. Рабочий день — day = [d0, d1].

Верните по возрастанию все максимальные отрезки внутри дня, где одновременно свободны не меньше need сотрудников и длина не меньше min_len. Отрезок — пара [from, to].

В работе: Синк на 9 человек, без кворума в 7 его не проводят: календарь сам предлагает окна от 30 минут.

Пример 1

Ввод
busy = [[[540, 600], [570, 630]], [[600, 660]], [[720, 780]]]
day = [540, 780]
need = 3
min_len = 30
Вывод
[[660, 720]]

У первого встречи сливаются в [540, 630). Все трое свободны на [660, 720) — 60 минут.

Пример 2

Ввод
busy = [[[540, 600]], [[560, 620]]]
day = [540, 660]
need = 1
min_len = 20
Вывод
[[540, 560], [600, 660]]

Хотя бы один свободен всегда, кроме [560, 600) — тогда заняты оба. Окна [540, 560) и [600, 660).

Ограничения

  • 1 ≤ число сотрудников ≤ 10³
  • 0 ≤ всего встреч ≤ 10⁵
  • 1 ≤ need
  • 1 ≤ min_len
  • 0 ≤ d0 ≤ d1 ≤ 10⁹
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def free_windows(busy, day, need, min_len):
ИнтервалыСканирующая прямаяСлияние интерваловцельO(n log n)

Источник: наша задача на данных Т-Банка. Условие пересказано своими словами.