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

125. Свежие посты из k лент

Средняя

Лента пользователя VK собирается из k источников: друзья и сообщества. Для каждого источника есть список feeds[i] — время публикации постов в секундах, от новых к старым.

Верните m самых свежих постов по всем источникам, от новых к старым. Если всего постов меньше m, верните все.

Посты с одинаковым временем считаются разными и оба попадают в ответ.

В работе: Первый экран ленты — 20 постов из 300 подписок: читать все 300 лент до конца не нужно.

Пример 1

Ввод
feeds = [[900, 500, 100], [800, 700], [950]]
m = 4
Вывод
[950, 900, 800, 700]

950 из третьей ленты, потом 900, 800, 700.

Пример 2

Ввод
feeds = [[30], [], [20, 10]]
m = 10
Вывод
[30, 20, 10]

Постов всего 3 — отдаём все.

Ограничения

  • 0 ≤ k ≤ 10⁴
  • суммарно постов ≤ 10⁶
  • 1 ≤ m ≤ 10⁴
  • каждый feeds[i] не возрастает
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def newest_posts(feeds, m):
КучаСлияние k списковцельO(n log n)

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