0619MediumGraph TheoryTopological SortDirected Acyclic Graph

Rounds of Inspection Tasks

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def minimum_semesters(n: int, relations: list[list[int]]) -> int:

Java

public int minimumSemesters(int n, int[][] relations)

The intended approach

Time O(n + m) where m = len(relations); each task and each requirement is handled once.Space O(n + m) for the adjacency list and the outstanding counts.

Build the forward adjacency list and, for each task, the number of requirements still outstanding. The tasks whose count is zero form the first round; running them all decrements the counts of their successors, and whichever successors reach zero form the next round. Peeling one whole group per iteration counts the rounds directly. The loop uses explicit lists rather than recursion, so a chain of 5000 tasks is fine. If the peeling finishes with some tasks never run, those tasks depend on each other in a loop, and the answer is -1.

Pythonentry point: minimum_semesters

def minimum_semesters(n, relations):
    # O(n + m) time, O(n + m) space. Count how many unfinished predecessors
    # each task still has. Everything with a count of zero can run right away,
    # and clearing that whole group is one round; clearing it drops the counts
    # of its successors, which reveals the next group. Peeling group by group
    # with an explicit queue keeps the work linear and never recurses. If the
    # peeling stops before every task has run, the leftover tasks depend on one
    # another in a loop and no schedule exists.
    waiting = [0] * (n + 1)
    successors = [[] for _ in range(n + 1)]
    for before, after in relations:
        successors[before].append(after)
        waiting[after] += 1
    group = [task for task in range(1, n + 1) if waiting[task] == 0]
    finished = 0
    rounds = 0
    while group:
        rounds += 1
        following = []
        for task in group:
            finished += 1
            for nxt in successors[task]:
                waiting[nxt] -= 1
                if waiting[nxt] == 0:
                    following.append(nxt)
        group = following
    return rounds if finished == n else -1

The obvious version

Give every task a tentative round number of 1 and then sweep the whole requirement list n times, each time pushing a successor later whenever it is not yet strictly after its predecessor. A run of n sweeps is enough for the numbers to settle when the requirements are satisfiable, so if one more sweep would still push something later the requirements contain a loop and -1 is reported. Otherwise the largest round number is the answer.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_minimum_semesters(n, relations):
    depth = [1] * (n + 1)
    for _ in range(n):
        for before, after in relations:
            if depth[before] + 1 > depth[after]:
                depth[after] = depth[before] + 1
    for before, after in relations:
        if depth[before] + 1 > depth[after]:
            return -1
    best = 0
    for task in range(1, n + 1):
        if depth[task] > best:
            best = depth[task]
    return best

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in