PreviousNext
Coding/Dynamic programming

Minimum project duration

Write codeHard35 min

Your task

You are given a DAG of n tasks (0..n-1) as edges [u, v] meaning task u must complete before task v starts, plus a duration[i] for each task. A task can start only after all its prerequisites finish, and independent tasks run in parallel. Return the minimum total time to finish all tasks (the length of the longest weighted path through the DAG, where a node's weight is its duration). The input is guaranteed acyclic.

Examples

min_project_time(n: int, edges: list[list[int]], duration: list[int]) -> int
Example 1
Inputmin_project_time(3, [[0, 2], [1, 2]], [3, 2, 5])
Output8