Minimum Months to Complete All Build Stages
A build system runs stages, each taking a fixed duration. A stage can start only after all its prerequisites finish, but independent stages run in parallel. Find the minimum total time to finish everything.
Problem
Given n stages (1-indexed) where time[i-1] is the months stage i takes, and relations where [prev, next] means stage prev must complete before stage next begins, return the minimum number of months to complete all stages. Independent stages run simultaneously. The dependency graph is a DAG.
Input
An integer n, a list relations of [prev, next] prerequisite edges, and an array time of durations.
Output
An integer: the minimum total months.
Constraints
- 1 <= n <= 50000
- 0 <= relations.length <= 50000
- 1 <= time[i] <= 10^4; the graph is acyclic.
Examples
Example 1
Input
n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
Output
8
Stages 1 and 2 run in parallel (max 3), then stage 3 takes 5: 3 + 5 = 8.
Example 2
Input
n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
Output
12
The critical path 3 -> 4 -> 5 sums to 3 + 4 + 5 = 12.