Parallel Courses III

How it works

Instead of working backwards from end nodes (DFS approach), we can work forwards from start nodes using topological sort. Kahn's algorithm processes nodes in dependency order, ensuring that when we process a course, all its prerequisites have already been processed.

For each course, we track the maximum time needed to reach it (including its own duration). When we process a course, we update all its dependents by propagating the maximum completion time. This naturally computes the longest weighted path through the graph.

Steps

1. Build an adjacency list and compute in-degrees for all courses.
2. Initialize each course's max time to its own duration.
3. Add all courses with in-degree 0 to the queue.
4. Process courses in topological order:
   • For each dependent course, update its max time to be the maximum of its current value and the predecessor's time plus its own duration.
   • Decrement the in-degree and add to the queue when it reaches 0.
5. Return the maximum completion time across all courses.

Complexity

• Time complexity: O(V + E)
• Space complexity: O(V + E)

Where V is the number of courses and E is the number of prerequisites.

Things to watch for

Confusing This With the Basic Parallel Courses Problem

Unlike the simpler version where each course takes one semester, this problem assigns different durations to each course. The answer is not just the longest path by node count, but the longest path by total time. Each course's duration must be added to the path weight.

Incorrect Initialization of Course Times

When using topological sort, each course's initial time should be its own duration, not zero. Failing to initialize maxTime[i] = time[i] means courses with no prerequisites will incorrectly have zero completion time.

Building the Adjacency List in the Wrong Direction

For the DFS approach, edges should point from prerequisites to dependent courses (forward direction). For some formulations, you might need to reverse this. Mixing up directions leads to computing minimum time to reach a course instead of minimum time from a course to complete all dependents.

Forgetting That Parallel Execution Means Taking the Maximum

When a course has multiple prerequisites, it cannot start until all prerequisites complete. This means taking the maximum completion time among all prerequisites, not the sum. Using addition instead of max will drastically overcount the total time.

Off-By-One Errors With 1-Indexed Courses

Course numbers are often 1-indexed in the input, but the time array is 0-indexed. Accessing time[course] instead of time[course - 1] causes array index out of bounds or incorrect time values.

from collections import deque

class Solution:
    def minimumTime(self, n: int, relations: list[list[int]], time: list[int]) -> int:
        adj = [[] for _ in range(n)]
        indegree = [0] * n
        maxTime = time[:]

        for src, dst in relations:
            adj[src - 1].append(dst - 1)
            indegree[dst - 1] += 1

        queue = deque([i for i in range(n) if indegree[i] == 0])
        while queue:
            node = queue.popleft()
            for nei in adj[node]:
                maxTime[nei] = max(maxTime[nei], maxTime[node] + time[nei])
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        return max(maxTime)

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        vector<vector<int>> adj(n);
        vector<int> indegree(n, 0);
        vector<int> maxTime(time.begin(), time.end());

        for (auto& relation : relations) {
            int src = relation[0] - 1, dst = relation[1] - 1;
            adj[src].push_back(dst);
            indegree[dst]++;
        }

        queue<int> queue;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue.push(i);
            }
        }

        while (!queue.empty()) {
            int node = queue.front(); queue.pop();
            for (int nei : adj[node]) {
                maxTime[nei] = max(maxTime[nei], maxTime[node] + time[nei]);
                if (--indegree[nei] == 0) {
                    queue.push(nei);
                }
            }
        }

        return *max_element(maxTime.begin(), maxTime.end());
    }
};