Fewest Work Rounds
MediumGraphs
Problem
A team must complete n tasks numbered 0 to n - 1. Each entry [a, b] of deps means task a must be finished in an earlier round than task b.
In each round the team can complete any number of tasks, as long as all of their prerequisites were completed in earlier rounds. Return the minimum number of rounds needed to finish every task, or -1 if that is impossible.
Example 1
- Input:
- n = 4, deps = [[0, 2], [1, 2], [2, 3]]
- Output:
- 3
Round 1: tasks 0 and 1. Round 2: task 2. Round 3: task 3.
Example 2
- Input:
- n = 3, deps = [[0, 1], [1, 2], [2, 0]]
- Output:
- -1
The tasks wait on each other in a circle.
Example 3
- Input:
- n = 3, deps = []
- Output:
- 1
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ deps.length ≤ 5·10^4
- 0 ≤ a, b < n
Hint
Show the first hint
In the first round, which tasks can you do? Is there any reason to delay a task that is ready?
Walkthrough
How to approach it
01Clarify before coding
- Is there a limit on tasks per round? No, any number.
- What if there is a cycle? Return -1.
- Can deps repeat? Yes; count and remove each copy consistently.
02Brute force
Simulate rounds by scanning all tasks each round and checking every dependency to see which tasks are now allowed.
Cost: Up to n rounds × O(n + m) per scan = O(n · (n + m)), 6·10^8 steps for a long chain.
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.