All problems

Project Finish Time

Medium · topological sort

A project is made of n tasks, numbered 0 to n - 1. Task i takes durations[i] hours. Some tasks depend on others: each pair [a, b] in deps means task b may only start once task a has finished.

You have as many workers as you need, so any number of tasks can run at the same time, and a task starts the moment all the tasks it depends on are done (tasks with no dependencies start at hour 0).

Return the number of hours until every task has finished. If the dependencies loop back on themselves, so that some task could never start, return -1.

The same pair may appear more than once, and a pair may even make a task depend on itself.

Examples

Example 1

Input: durations = [3, 2, 4], deps = [[0, 1], [0, 2]]

Output: 7

Task 0 ends at hour 3. Tasks 1 and 2 then run side by side, ending at hours 5 and 7.

Example 2

Input: durations = [1, 1], deps = [[0, 1], [1, 0]]

Output: -1

Each task waits for the other, so neither can ever start.

Example 3

Input: durations = [2, 3, 1, 4], deps = [[0, 1], [1, 3], [2, 3]]

Output: 9

Task 3 must wait for task 1, which ends at hour 5 (after task 0), so it ends at hour 9. Task 2 is not the bottleneck.

Constraints