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

197. Блоки эфиров с суммой зрителей

Средняя

Эфир VK Видео — тройка [start, end, viewers]: минуты начала и конца и число зрителей эфира.

Эфиры, которые пересекаются или касаются (start одного не больше end другого), относятся к одному блоку; цепочки пересечений тоже склеиваются. Для каждого блока верните [начало, конец, сумма зрителей], блоки — по возрастанию начала.

В работе: Рекламный отдел продаёт слоты между блоками эфиров: за вечер 900 эфиров разных авторов, и нужно знать, где окна и сколько зрителей в каждом блоке.

Пример 1

Ввод
streams = [[1080, 1140, 5200], [1130, 1200, 800], [1260, 1300, 1500], [1190, 1210, 300]]
Вывод
[[1080, 1210, 6300], [1260, 1300, 1500]]

Три первых по времени эфира склеены цепочкой: 1080–1210, зрителей 6300.

Пример 2

Ввод
streams = [[0, 10, 1], [10, 20, 2]]
Вывод
[[0, 20, 3]]

Касание тоже склеивает.

Ограничения

  • 0 ≤ n ≤ 10⁵
  • 0 ≤ start ≤ end ≤ 10⁹
  • 0 ≤ viewers ≤ 10⁶
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def stream_blocks(streams):
ИнтервалыСортировкаСлияние отрезковцельO(n log n)

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