Parallel Courses III — Hard Problem & Solution

Problem statement

A CodeKairo track has n courses labelled 1 to n. Each relations[j] = [prevCourse, nextCourse] says prevCourse must be finished before nextCourse can start. Course i takes time[i - 1] months.

You may start any course as soon as all its prerequisites are finished, and you may take any number of courses at the same time.

Return the minimum number of months needed to finish every course. The prerequisites are guaranteed to form a directed acyclic graph, so finishing is always possible.

Example 1

Input: n = 4, relations = [[1,2],[1,3],[2,4],[3,4]], time = [2,5,3,1]
Output: 8
Explanation: Course 1 ends at month 2, course 2 at 7, course 3 at 5, so course 4 starts at 7 and ends at 8.

Example 2

Input: n = 3, relations = [], time = [4,9,2]
Output: 9
Explanation: Everything runs in parallel; the longest course decides.

Example 3

Input: n = 5, relations = [[2,1],[3,1],[4,3]], time = [1,6,2,7,3]
Output: 10

Constraints

• 1 <= n <= 5 * 10^4
• 0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10^4)
• relations[j].length == 2
• 1 <= prevCourse, nextCourse <= n
• prevCourse != nextCourse
• all pairs [prevCourse, nextCourse] are unique
• time.length == n
• 1 <= time[i] <= 10^4
• the relations form a directed acyclic graph

How to solve Parallel Courses III

With unlimited parallelism the schedule is the critical path of the DAG: finish(v) = time(v) + max(finish(p)) over prerequisites p, computed in topological order.

Approach

1. Build adjacency lists and in-degrees from relations; let start[v] = 0 for all courses.
2. Queue every course with in-degree 0.
3. Pop u; its finish time is start[u] + time[u]. For each dependent v, set start[v] = max(start[v], finish(u)), decrement its in-degree and queue it at 0.
4. Return the largest finish time seen.

Why it works

When a course is popped, all its prerequisites were popped before it, so start[u] already equals the latest finish among them — the earliest moment it may begin. Starting every course at that moment is optimal since nothing is gained by waiting, and the whole program ends when the last course does.

Complexity

• Time — O(n + m)
• Space — O(n + m)

Pitfalls

• Courses are 1-indexed in relations but time is 0-indexed.
• The answer is the maximum finish over all courses, not the finish of the last course popped.
• Courses with no relations at all still count — they run from month 0.

Reference solution

Python

from typing import List
from collections import deque

def minimumTime(n: int, relations: List[List[int]], time: List[int]) -> int:
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in relations:
        adj[a - 1].append(b - 1)
        indeg[b - 1] += 1
    start = [0] * n
    q = deque(i for i in range(n) if indeg[i] == 0)
    best = 0
    while q:
        u = q.popleft()
        finish = start[u] + time[u]
        if finish > best:
            best = finish
        for v in adj[u]:
            if finish > start[v]:
                start[v] = finish
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return best

JavaScript

var minimumTime = function(n, relations, time) {
    var adj = [], indeg = [], start = [];
    for (var i = 0; i < n; i++) { adj.push([]); indeg.push(0); start.push(0); }
    for (var r = 0; r < relations.length; r++) {
        adj[relations[r][0] - 1].push(relations[r][1] - 1);
        indeg[relations[r][1] - 1]++;
    }
    var queue = [];
    for (var s = 0; s < n; s++) if (indeg[s] === 0) queue.push(s);
    var best = 0;
    for (var h = 0; h < queue.length; h++) {
        var u = queue[h];
        var finish = start[u] + time[u];
        if (finish > best) best = finish;
        for (var j = 0; j < adj[u].length; j++) {
            var v = adj[u][j];
            if (finish > start[v]) start[v] = finish;
            if (--indeg[v] === 0) queue.push(v);
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Remove Boxes Hard
• Number of Squareful Arrays Hard
• Closest Subsequence Sum Hard
• Maximum Number of Achievable Transfer Requests Hard
• 24 Game Hard
• Verbal Arithmetic Puzzle Hard