Parallel Courses III

113.4k
0

There are n courses labeled from 1 to n. Array time stores duration of every course, and relations stores prerequisite pairs [prevCourse, nextCourse].

A course can start as soon as all prerequisites are completed. Any number of ready courses can run in parallel. Return the minimum number of months required to complete all courses.

Example 1

Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5]

Output: 8

Explanation: Course 1 and course 2 start together. Course 3 starts after month 3, so total months become 3 + 5 = 8.

Example 2

Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]

Output: 12

Explanation: Course 4 finishes at month 7. Course 5 can start only after month 7, so final completion month is 12.

Approach 1

The course plan forms a directed acyclic graph where every prerequisite edge points from an earlier course to a dependent course. Since independent courses can run in parallel, the total completion time equals the duration of the longest weighted dependency chain rather than the sum of all course durations.

DFS with memoization calculates the longest completion span beginning from each course. The result for a course combines the course duration with the longest span among all dependent courses.

Algorithm

  • Build an adjacency list containing edges from every prerequisite course to the corresponding dependent courses.

  • Initialize a memo array of size N, where each entry stores the longest completion span beginning from a course.

  • During DFS, return the cached value when available, avoiding repeated calculation of shared dependency paths.

  • Explore every dependent course and retain the maximum returned span, since dependent branches can proceed in parallel.

  • Store the current course duration plus the maximum dependent span in memo, representing the longest chain beginning from the current course.

  • Run DFS from every course and return the largest memoized span, as the longest weighted dependency chain determines the total completion time.

Note: A prerequisite chain containing up to N courses can produce DFS recursion depth O(N), which may exceed the call-stack limit for large inputs. Kahn’s Algorithm uses an iterative queue and avoids recursion-depth concerns.

Dry Run

parallel_courses_iii_dfs_corrected

parallel_courses_iii_dfs_corrected

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns longest completion time starting from one course.
int dfs(int course, vector<vector<int>>& graph, vector<int>& time, vector<int>& memo) {
// Base case: cached value avoids repeated dependency-chain work.
if (memo[course] != 0) {
return memo[course];
}
int bestNext = 0;
// Explore every course dependent on current course.
for (int nextCourse : graph[course]) {
// Keep the longest dependent chain.
bestNext = max(bestNext, dfs(nextCourse, graph, time, memo));
}
// Add current course duration to the longest dependent chain.
memo[course] = time[course - 1] + bestNext;
// Return the longest finish time from current course.
return memo[course];
}
public:
// Returns minimum months needed to finish all courses.
int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
vector<vector<int>> graph(n + 1);
// Build forward prerequisite graph.
for (vector<int>& edge : relations) {
int prevCourse = edge[0];
int nextCourse = edge[1];
graph[prevCourse].push_back(nextCourse);
}
vector<int> memo(n + 1, 0);
int answer = 0;
// Try every course as the starting point of a chain.
for (int course = 1; course <= n; course++) {
// Store the maximum chain completion time.
answer = max(answer, dfs(course, graph, time, memo));
}
// Return the minimum total months.
return answer;
}
};
// Driver code.
int main() {
int n = 3;
vector<vector<int>> relations = {
{1, 3},
{2, 3}
};
vector<int> time = {3, 2, 5};
Solution sol;
cout << sol.minimumTime(n, relations, time);
return 0;
}

Complexity Analysis

Time Complexity: O(N+E), where N is the number of courses and E is the number of prerequisite relations; memoization processes every course and edge once.

Space Complexity: O(N+E), where the adjacency list stores N courses and E edges, while the memo array and recursion stack require O(N) space.

Approach 2

Kahn’s Algorithm processes courses in prerequisite order using indegrees. Courses having indegree 0 can begin immediately, so the earliest finish time for each starting course equals the corresponding duration.

For an edge from course u to course v, course v can finish only after u finishes. Taking the maximum finish time across all prerequisites accounts for parallel execution and preserves the longest required dependency chain.

Algorithm

  • Build an adjacency list and indegree array from all prerequisite relations, storing course dependencies and pending prerequisite counts.

  • Add every course having indegree 0 to a queue and set the finish time to the course duration, since no earlier course delays the start.

  • Continue processing while the queue contains courses, removing the front course in valid prerequisite order.

  • For every dependent course, update the finish time with max(finish[dependent], finish[current]+time[dependent]).

  • Reduce the dependent course’s indegree after processing each prerequisite, representing one completed incoming dependency.

  • Add the dependent course to the queue when the indegree becomes 0, as all required prerequisites have now been processed.

  • Return the maximum value in the finish-time array, representing the earliest month by which all courses can be completed.

Dry Run

parallel_courses_iii_bfs_corrected

parallel_courses_iii_bfs_corrected

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns minimum months needed to finish all courses.
int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
vector<vector<int>> graph(n + 1);
vector<int> indegree(n + 1, 0);
// Build graph and count prerequisites for each course.
for (vector<int>& edge : relations) {
int prevCourse = edge[0];
int nextCourse = edge[1];
graph[prevCourse].push_back(nextCourse);
indegree[nextCourse]++;
}
queue<int> q;
vector<int> finishTime(n + 1, 0);
// Add courses without prerequisites to the queue.
for (int course = 1; course <= n; course++) {
// A course with zero indegree can start immediately.
if (indegree[course] == 0) {
finishTime[course] = time[course - 1];
q.push(course);
}
}
int answer = 0;
// Process courses in topological order.
while (!q.empty()) {
int course = q.front();
q.pop();
// Keep the maximum finish time seen so far.
answer = max(answer, finishTime[course]);
// Propagate best finish time to every dependent course.
for (int nextCourse : graph[course]) {
finishTime[nextCourse] = max(
finishTime[nextCourse],
finishTime[course] + time[nextCourse - 1]
);
// Mark one prerequisite as completed.
indegree[nextCourse]--;
// Dependent course becomes ready after all prerequisites.
if (indegree[nextCourse] == 0) {
q.push(nextCourse);
}
}
}
// Return the minimum total months.
return answer;
}
};
// Driver code.
int main() {
int n = 3;
vector<vector<int>> relations = {
{1, 3},
{2, 3}
};
vector<int> time = {3, 2, 5};
Solution sol;
cout << sol.minimumTime(n, relations, time);
return 0;
}

Complexity Analysis

Time Complexity: O(N+E), where N is the number of courses and E is the number of prerequisite relations; graph construction and traversal process each course and edge once.

Space Complexity: O(N+E), where the adjacency list stores N courses and E edges, while the indegree, queue, and finish-time arrays require O(N) space.

Interview follow-up Questions

Parallel branches can run together, so only the slowest prerequisite chain determines final completion month.

Graph

Read Similar Blogs

Graph

Disjoint Set Union: Union by Rank, Size and Path Compression

Input: N = 5 , operations = [unionByRank(1,2), unionByRank(2,3), find(1,3), find(1,5)] Output: [true, false] Explanation: Rank-based merges place nodes 1 , 2 , and 3 in one set. Node 5 remains in a...

89.1k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weig...

96.1k
Graph

Network Delay Time Using Dijkstra's Algorithm

A network contains n nodes labeled from 1 to n . Each directed edge [u,v,w] means a signal needs w time units to travel from node u to node v . A signal starts from node k . Return the minimum time...

81.2k
Comments0