FunctionRacerProblemsRace

Rounds of Parallel Jobs

MediumGraphsPython, JavaScript, TypeScript, Java, C++

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

n 4
before [[0,1],[0,2],[2,3]]
returns 3

Round 1 runs job 0; round 2 runs 1 and 2 together; round 3 runs 3.

Example 2

n 3
before [[0,1],[1,2],[2,0]]
returns -1

Each job waits for another in a circle, so none of them ever starts.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems