Rounds of Parallel Jobs
A workshop has n jobs numbered 0 to n - 1. before is a list of pairs [a, b] with a != b: job a must be finished before job b can start; the same pair may appear more than once. Work happens in rounds. In every round, all jobs whose requirements are already finished run at the same time, and they are all finished by the end of that round. A job with no requirement runs in round 1.
Return the number of rounds needed to finish every job. Return -1 when some job can never start because the requirements run in a circle.
Example 1
Round 1 runs job 0; round 2 runs 1 and 2 together; round 3 runs 3.
Example 2
Each job waits for another in a circle, so none of them ever starts.
Constraints
1 <= n <= 500 <= len(before) <= 1000 <= a, b <= n - 1anda != b
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Sealed RoomsMedium
- Smallest Task OrderMedium
- Smallest Team SplitMedium
- Steps to the ExitMedium
- Through the CheckpointMedium
- Towns Within BudgetMedium
- Break Through WallsHard
- Collect Every KeyHard