Show problems as
Classic problem #1136MediumGraph TheoryTopological SortDirected Acyclic Graph

Parallel Courses

Real-world version: Rounds of Inspection Tasks
Tracked in this browser only
Read Parallel Courses on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A plant has n inspection tasks, numbered 1 through n. Ordering requirements arrive as an edge list: each entry relations[i] = [before_i, after_i] is a directed requirement saying that task before_i has to be finished in a round strictly earlier than the round that runs task after_i. The pair is ordered, so [u, v] and [v, u] mean different things, and no entry names the same task twice.

Work proceeds in rounds. In one round you may run as many tasks as you like, as long as every task you run has all of its requirements already finished in earlier rounds. A task with no requirements can run in the first round. Tasks that appear in no requirement at all still have to be run.

Return the smallest number of rounds that finishes every task, or -1 if the requirements cannot all be met. Since a valid answer is always at least 1, -1 cannot be confused with a real answer.

Examples

Example 1

Input
n = 4, relations = [[1, 2], [1, 3], [2, 4], [3, 4]]
Output
3

Round 1 runs task 1, round 2 runs tasks 2 and 3 together, round 3 runs task 4. Every requirement is met because each `before` task sits in an earlier round than its `after` task.

Example 2

Input
n = 4, relations = [[1, 2]]
Output
2

Tasks 3 and 4 appear in no requirement, so they can run in round 1 alongside task 1; task 2 then runs in round 2.

Example 3

Input
n = 3, relations = [[1, 2], [2, 3], [3, 1]]
Output
-1

Each of the three tasks has to sit in an earlier round than the next, and task 3 has to sit earlier than task 1, so no assignment of rounds can satisfy all three requirements.

Constraints

  • 1 <= n <= 5000
  • 1 <= relations.length <= 5000
  • relations[i].length == 2
  • 1 <= before_i, after_i <= n
  • before_i != after_i
  • All the pairs [before_i, after_i] are distinct.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def minimum_semesters(n: int, relations: list[list[int]]) -> int:
Java
public int minimumSemesters(int n, int[][] relations)

More on the same topics