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

187. Медиана времени доставки после каждого заказа

Средняя

Заказы Яндекс Еды приходят по одному, minutes[i] — сколько минут ехал i-й заказ.

После каждого заказа нужна медиана всех известных к этому моменту времён. При чётном числе заказов берите нижнюю медиану — меньшее из двух средних значений. Верните список медиан.

В работе: Табло ресторана в кабинете партнёра показывает медиану доставки за смену и обновляет её после каждого заказа: в вечерний пик 3000 заказов в час на город.

Пример 1

Ввод
minutes = [34, 25, 41, 28, 60]
Вывод
[34, 25, 34, 28, 34]

После четырёх заказов отсортировано 25, 28, 34, 41 — нижняя медиана 28.

Пример 2

Ввод
minutes = [30]
Вывод
[30]

Ограничения

  • 1 ≤ n ≤ 10⁵
  • 1 ≤ minutes[i] ≤ 300
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def running_median(minutes):
КучаДве кучиПоток данныхцельO(n log n)

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