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

123. Пик нагрузки звонков и время над порогом

Сложная

Каждый звонок VK Звонков — тройка [start, end, weight]: с секунды start до секунды end (не включая end) он нагружает медиасервер на weight Мбит/с.

Верните [peak, over]: наибольшую суммарную нагрузку и суммарное число секунд, когда нагрузка строго больше threshold. Без звонков ответ [0, 0].

В работе: Сервер держит 10 Гбит/с. Если нагрузка выше порога больше 20 минут в сутки, кластер пора расширять.

Пример 1

Ввод
calls = [[0, 10, 3], [5, 15, 4], [10, 20, 2]]
threshold = 3
Вывод
[7, 10]

Нагрузка: 3 на [0, 5), 7 на [5, 10), 6 на [10, 15), 2 на [15, 20). Пик 7, выше 3 — 10 секунд.

Пример 2

Ввод
calls = [[0, 5, 2], [5, 10, 2]]
threshold = 2
Вывод
[2, 0]

Один звонок кончился, другой начался в ту же секунду: пик 2, а не 4.

Ограничения

  • 0 ≤ длина calls ≤ 10⁵
  • 0 ≤ start < end ≤ 10⁹
  • 1 ≤ weight ≤ 10⁴
  • 0 ≤ threshold
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def peak_load(calls, threshold):
ИнтервалыСканирующая прямаяСортировка событийцельO(n log n)

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