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

99. Когда закончится ночной расчёт

Сложная

Ночной расчёт в банке — это n джобов: выгрузки платежей, сверка, витрины. Джоб i работает dur[i] минут. Зависимость [a, b] значит: b стартует только после того, как закончился a.

Серверов хватает на все джобы сразу, каждый стартует, как только готовы его зависимости. Верните, через сколько минут закончится весь расчёт, или -1, если зависимости зациклены и расчёт не закончится никогда.

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

Пример 1

Ввод
dur = [30, 20, 50, 10]
deps = [[0, 3], [1, 2], [2, 3]]
Вывод
80

Цепочка 1 → 2 → 3 идёт 20 + 50 + 10 = 80 минут, джоб 0 успевает параллельно.

Пример 2

Ввод
dur = [5, 5]
deps = [[0, 1], [1, 0]]
Вывод
-1

Джобы ждут друг друга.

Ограничения

  • 1 ≤ n ≤ 2·10⁵
  • 0 ≤ число зависимостей ≤ 5·10⁵
  • 1 ≤ dur[i] ≤ 600
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def batch_finish_time(dur, deps):
ГрафыТопологическая сортировкаКритический путьцельO(n)

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