A workflow has n jobs numbered 0 .. n-1; job i takes duration[i] time units. The list deps contains pairs [a, b] meaning job b cannot start until job a has finished. Any number of jobs may run in parallel, and a job starts as soon as all the jobs it depends on are finished (jobs with no dependencies start at time 0).
Return a list finish where finish[i] is the earliest time at which job i can be finished. If the dependencies contain a cycle, return [].
Examples
Input: duration = [3, 2, 4], deps = [[0, 1], [0, 2]]
Output: [3, 5, 7]
Explanation: job 0 runs 0..3; jobs 1 and 2 both start at 3 and finish at 5 and 7.
Input: duration = [2, 1, 3], deps = [[0, 2], [1, 2]]
Output: [2, 1, 5]
Input: duration = [1, 1], deps = [[0, 1], [1, 0]]
Output: []
Constraints
1 <= n <= 10**4,1 <= duration[i] <= 10**6,0 <= len(deps) <= 3 * 10**4- Target: O(V + E) time.
Goals
- Compute earliest start times as a maximum over predecessors in topological order
- Return per-node results and a sentinel on cycles