Critical Path Finish Time
HardGraphs
Problem
A construction project has tasks numbered 0 to n - 1, where n = durations.length; task i takes durations[i] days. Each entry [a, b] of deps means task b cannot start until task a has finished.
There are unlimited crews, so any task may start the moment all of its prerequisites are finished. The project starts at day 0. Return the day on which the last task finishes, or -1 if the dependencies are circular.
Example 1
- Input:
- durations = [3, 2, 5, 1], deps = [[0, 2], [1, 2], [2, 3]]
- Output:
- 9
Task 2 waits for task 0 (done day 3) and task 1 (day 2), runs days 3–8, and task 3 finishes on day 9.
Example 2
- Input:
- durations = [2, 4, 1], deps = [[0, 1], [1, 2], [2, 0]]
- Output:
- -1
Example 3
- Input:
- durations = [1, 2, 3, 4, 5], deps = []
- Output:
- 5
Everything runs in parallel; the longest task decides.
Constraints
- 1 ≤ n ≤ 5·10^4
- 1 ≤ durations[i] ≤ 10^4
- 0 ≤ deps.length ≤ 5·10^4
- 0 ≤ a, b < n
Hint
Show the first hint
When is the earliest moment a task can start?
Walkthrough
How to approach it
01Clarify before coding
- Is the number of crews limited? No, so the only constraint is precedence.
- What if dependencies form a cycle? Return -1.
- Do tasks with no dependencies start at day 0? Yes.
02Brute force
Simulate day by day, starting every task whose prerequisites are all finished and advancing running tasks.
Cost: O(D · (n + m)) where D can reach 5·10^8 days in a long chain: far too slow.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.