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

126. Окно, где абонента видели все вышки

Сложная

Телефон абонента МТС ловят k базовых станций. Для каждой есть список pings[i] — минуты с начала суток, когда станция видела телефон, по возрастанию, без пустых списков.

Найдите отрезок [lo, hi] наименьшей длины hi - lo, в который каждая станция отметила телефон хотя бы раз. Концы — значения из списков.

Если таких отрезков несколько, верните тот, у которого lo меньше.

В работе: Оценка положения по трём и более станциям: чем короче окно, где отметились все, тем точнее триангуляция.

Пример 1

Ввод
pings = [[4, 10, 15, 24], [0, 9, 12, 20], [5, 18, 22, 30]]
Вывод
[20, 24]

В [20, 24] есть 24, 20 и 22 — длина 4.

Пример 2

Ввод
pings = [[7, 8], [8, 9]]
Вывод
[8, 8]

Обе видели телефон в минуту 8: окно нулевой длины.

Ограничения

  • 1 ≤ k ≤ 3500
  • 1 ≤ длина pings[i] ≤ 50
  • суммарно отметок ≤ 10⁵
  • 0 ≤ pings[i][j] ≤ 10⁹
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def tower_window(pings):
КучаСлияние k списковОкно по k потокамцельO(n log n)

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