Critical path makespan
A build system runs n tasks (0..n-1), each with a positive duration durations[i]. Dependencies are pairs [a, b] meaning task b can only start after task a finishes; independent tasks run fully in parallel. Return the makespan — the minimum total time to finish all tasks given unlimited parallelism — which equals the longest dependency chain weighted by durations (the critical path). If the dependencies form a cycle, return -1.
Implement
critical_path(durations: list[int], deps: list[list[int]]) → intExamples
in
[[3,2,5,1],[[0,1],[1,3],[0,2],[2,3]]]out9What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 30 min
solution.py
InputExpectedGot
[[3,2,5,1],[[0,1],[1,3],[0,2],[2,3]]]9not run yetsample