Parallel Courses III

Hard
1532.

Parallel Courses III

Parallel Courses III is a hard coding problem on arrays, dynamic programming and graph, asked in Amazon, Google and Two Sigma interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} relations
 * @param {number[]} time
 * @return {number}
 */
var minimumTime = function(n, relations, time) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Parallel Courses III — Solution in Python, Java & C++

Parallel Courses III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Parallel Courses III is a hard coding problem on arrays, dynamic programming and graph, asked in Amazon, Google and Two Sigma interviews.

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

Hints for Parallel Courses III

  1. Hint 1

    A course can finish no earlier than its own duration plus the latest finish time among its prerequisites.

  2. Hint 2

    Compute finish times in an order where every prerequisite is handled before the courses that depend on it.

  3. Hint 3

    Kahn's topological sort gives that order: when a course is popped, push its finish time forward to each dependent course as that course's earliest start. The answer is the largest finish time.

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

Java

public static int minimumTime(int n, int[][] relations, int[] time) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    int[] indeg = new int[n];
    for (int[] r : relations) { adj.get(r[0] - 1).add(r[1] - 1); indeg[r[1] - 1]++; }
    int[] start = new int[n];
    int[] queue = new int[n];
    int head = 0, tail = 0;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) queue[tail++] = i;
    int best = 0;
    while (head < tail) {
        int u = queue[head++];
        int finish = start[u] + time[u];
        best = Math.max(best, finish);
        for (int v : adj.get(u)) {
            if (finish > start[v]) start[v] = finish;
            if (--indeg[v] == 0) queue[tail++] = v;
        }
    }
    return best;
}

C++

int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0), start(n, 0), queue;
    for (auto& r : relations) { adj[r[0] - 1].push_back(r[1] - 1); indeg[r[1] - 1]++; }
    for (int i = 0; i < n; i++) if (indeg[i] == 0) queue.push_back(i);
    int best = 0;
    for (size_t h = 0; h < queue.size(); h++) {
        int u = queue[h];
        int finish = start[u] + time[u];
        best = max(best, finish);
        for (int v : adj[u]) {
            if (finish > start[v]) start[v] = finish;
            if (--indeg[v] == 0) queue.push_back(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming