Самый быстрый учебный план

Сложная

В программе обучения course_count курсов с номерами от 1 до course_count. Курс с номером i длится durations[i - 1] месяцев. Некоторые курсы можно начать только после других: пара [a, b] в списке prereqs означает, что курс a нужно закончить до начала курса b. Курс можно начать в любой момент, когда пройдены все курсы, от которых он зависит. Одновременно можно проходить сколько угодно курсов. Верните наименьшее число месяцев, за которое можно пройти всю программу. Циклических зависимостей нет.

Пример 1

course_count=4, prereqs=[[1, 2], [1, 3], [3, 4]], durations=[2, 6, 1, 3] → 8

Курс 1 закончится через 2 месяца. Курс 2 идёт после него и закончится к 2 + 6 = 8. Курсы 3 и 4 закончатся к 2 + 1 + 3 = 6. Всё готово через 8 месяцев.

Пример 2

course_count=3, prereqs=[], durations=[4, 9, 2] → 9

Зависимостей нет, все курсы идут одновременно — ждём самый долгий, 9 месяцев.

Пример 3

course_count=3, prereqs=[[2, 1], [3, 1]], durations=[5, 1, 4] → 9

Ограничения

1 ≤ course_count ≤ 5·10⁴
0 ≤ len(prereqs) ≤ min(course_count·(course_count − 1)/2, 5·10⁴)
prereqs[j] = [a, b], 1 ≤ a, b ≤ course_count, a ≠ b
Все пары в prereqs различны, зависимости не образуют цикла
len(durations) = course_count
1 ≤ durations[i] ≤ 10⁴

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Graph Topological Sort Array Dynamic Programming

Вход

course_count=4, prereqs=[[1, 2], [1, 3], [3, 4]], durations=[2, 6, 1, 3]

Ожидается

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 63 теста на сервере, включая скрытые.