2050. Parallel Courses III
Problem Description
In this problem, you are tasked with finding the minimum number of months needed to complete a set of courses with certain prerequisites. There are n
courses labeled from 1
to n
. A 2D integer array relations
is given, where each pair [prevCourse, nextCourse]
signifies that the prevCourse
must be completed before the nextCourse
can be taken. You also have an array time
representing the number of months required to complete each course, indexed at 0
. There are two key rules you must follow: you can start any course at any time as long as its prerequisites are satisfied, and you can take as many courses concurrently as you desire. The task is to calculate the minimum total time needed to complete all courses, under the constraint that a direct acyclic graph (DAG) represents the course structure.
Intuition
To solve this problem, we need to process courses in a way that respects prerequisite relations and keeps track of the total time needed to complete each course individually, as well as the overall time to finish all courses. This lends itself to a topological sort approach, where we:
- Determine the prerequisites (in-degree) for each course.
- Create a graph representing the course dependencies.
- Use a queue to process courses that have no prerequisites.
- Keep an array (
f
) to store the finishing time for each course, based on its prerequisites' finishing times. - Use a variable (
ans
) to maintain the maximum finishing time across all courses.
The provided solution iterates through the courses, initializing a queue with those that have no prerequisites and setting their finishing time in the array f
using the time
array. We then go through the courses in the queue one by one, updating the finishing time for their dependent courses and ensuring we take the maximum time between the time already recorded for that course and the finishing time of the current course plus the time required for the dependent course. We decrement the in-degree of each dependent course and add it to the queue if its in-degree drops to zero.
Using these steps, we guarantee that we process the courses such that prerequisites are always completed before dependent courses and that concurrency is maximized, as there are no restrictions on the number of courses that can be taken simultaneously. The final answer (ans
) represents the minimum number of months needed to complete all courses, as it accounts for the longest path through the graph, which effectively is the critical path that determines the overall time to completion.
Learn more about Graph, Topological Sort and Dynamic Programming patterns.
Solution Approach
The solution to this problem efficiently makes use of topological sorting, a common algorithm for processing Directed Acyclic Graphs (DAGs), alongside dynamic programming to calculate minimum times.
Data Structures:
- A graph
g
is represented as a dictionary of lists, mapping each course to its list of next courses. - An in-degree array
indeg
, which keeps track of how many prerequisites each course has. - A queue
q
, implemented as a deque, used for the topological sort. - An array
f
, used to store the finishing time for each course, or the minimum months needed to reach that course.
Algorithm Steps:
-
Graph and In-Degree Initialization: For each relation in
relations
, the graphg
and the in-degree arrayindeg
are populated. Every relation[a, b]
indicatesb
is dependent ona
, soa
is added to the list ofb
's prerequisites in the graph, andb
's in-degree is incremented since it has one more course that precedes it. -
Identifying Start Courses: We iterate over all courses. Those without prerequisites (
indeg[i] == 0
) are added to the queueq
, and their finishing timef[i]
is set to their respective time from thetime
array. -
Topological Sort and Finishing Time Calculation:
- While the queue is not empty:
- Dequeue an element
i
. - For each course
j
thati
is a prerequisite for:- Update the finishing time for course
j
(f[j]
) to be the maximum of the current stored time and the sum off[i]
and the time to complete coursej
. This ensuresf[j]
reflects the total time taken to reach coursej
after completing all its prerequisites. - Decrement the in-degree of course
j
. Ifj
's in-degree becomes 0, it means all its prerequisites are met, and it's added to the queue for processing.
- Update the finishing time for course
- Update the overall answer
ans
to be the maximum of its current value andf[j]
.
- Dequeue an element
- While the queue is not empty:
-
Result: After processing all courses,
ans
holds the minimum number of months required to complete all courses. This is becauseans
tracks the longest path (in months) through the graph, which corresponds to the time it would take to finish the courses if they were taken sequentially following their dependencies.
Conclusion:
The algorithm successfully computes the minimum time to finish all courses by leveraging topological sort to respect course prerequisites and dynamic programming to calculate the minimum finish times, taking advantage of the ability to take multiple courses concurrently. This solution ensures that all courses are processed in the correct order and that the time tracking reflects the concurrent nature of course enrollment.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example:
Imagine a scenario with 4 courses, where the time
array is given as time = [1, 2, 3, 1]
, which indicates that course 1 takes 1 month to complete, course 2 takes 2 months, and so on. The relations
array is given as relations = [[1, 3], [2, 3], [3, 4]]
, meaning course 1 and 2 are prerequisites for course 3, and course 3 is a prerequisite for course 4.
-
Graph and In-Degree Initialization:
- Initialize the graph
g
and in-degree arrayindeg
. - For
relations = [[1, 3], [2, 3], [3, 4]]
, we build the graphg = {1: [3], 2: [3], 3: [4]}
. The in-degree arrayindeg = [0, 0, 2, 1]
will have the count of prerequisites for each course.
- Initialize the graph
-
Identifying Start Courses:
- We see that course 1 and course 2 have zero prerequisites (
indeg[0] == 0
andindeg[1] == 0
). - Initialize the queue
q
with these courses and setf = [1, 2, 0, 0]
, wheref[0] = 1
andf[1] = 2
.
- We see that course 1 and course 2 have zero prerequisites (
-
Topological Sort and Finishing Time Calculation:
- Process the courses in the queue:
- Dequeue course 1, with finishing time of 1 month. Course 3 is a dependent, so update
f[2]
tomax(f[2], f[0] + time[2]) = max(0, 1 + 3) = 4
. - Decrease in-degree of course 3 (
indeg[2]
becomes 1). - Since in-degree of course 3 is not 0, it remains in the graph.
- Next, dequeue course 2, with a finishing time of 2 months. Again, course 3 is a dependent, so update
f[2]
tomax(f[2], f[1] + time[2]) = max(4, 2 + 3) = 5
. - Decrease in-degree of course 3 (
indeg[2]
becomes 0), and add course 3 to the queue. - Dequeue course 3, with finishing time of 5 months. Course 4 is a dependent, so update
f[3]
tomax(f[3], f[2] + time[3]) = max(0, 5 + 1) = 6
. - Decrease in-degree of course 4 (
indeg[3]
becomes 0), and add course 4 to the queue.
- Dequeue course 1, with finishing time of 1 month. Course 3 is a dependent, so update
- The queue is now empty, and we can calculate the maximum time from the array
f
, which isans = 6
months.
- Process the courses in the queue:
-
Result: We conclude that it will take a minimum of 6 months to complete all courses, given the ability to take multiple courses concurrently, and respecting the prerequisite requirements.
This walk-through illustrates the process of topological sorting, dynamic programming, and concurrent course enrollment utilized by the proposed solution to compute the minimum total time required to complete all the courses.
Solution Implementation
1from collections import defaultdict, deque
2from typing import List
3
4class Solution:
5 def minimumTime(self, total_tasks: int, prerequisites: List[List[int]], task_durations: List[int]) -> int:
6 # Create a graph using a dictionary and initialize in-degrees for all nodes.
7 graph = defaultdict(list)
8 in_degree = [0] * total_tasks
9
10 # Build the graph and update in-degrees based on prerequisites.
11 for start, end in prerequisites:
12 graph[start - 1].append(end - 1) # Adjusting indices to be 0-based.
13 in_degree[end - 1] += 1
14
15 # Initialize a queue for processing tasks with no prerequisites.
16 queue = deque()
17 # Initialize an array to keep track of the finish times of each task.
18 finish_times = [0] * total_tasks
19 # This will keep track of the global maximum time.
20 max_time = 0
21
22 # Enqueue tasks with no prerequisites and set their finish times.
23 for i, (in_deg, duration) in enumerate(zip(in_degree, task_durations)):
24 if in_deg == 0:
25 queue.append(i)
26 finish_times[i] = duration # The finish time is the task's own duration.
27 max_time = max(max_time, duration) # Check if this is the new max time.
28
29 # Process tasks in the queue.
30 while queue:
31 current_task = queue.popleft()
32 # Iterate through the current task's dependent tasks.
33 for dependent in graph[current_task]:
34 # Calculate the finish time of the dependent task.
35 finish_times[dependent] = max(finish_times[dependent], finish_times[current_task] + task_durations[dependent])
36 # Update the global maximum time.
37 max_time = max(max_time, finish_times[dependent])
38 # Decrease the in-degree of the dependent task.
39 in_degree[dependent] -= 1
40 # If the dependent task has no more prerequisites, add it to the queue.
41 if in_degree[dependent] == 0:
42 queue.append(dependent)
43
44 # Return the global maximum time, which is the minimum time to complete all tasks.
45 return max_time
46
1class Solution {
2
3 public int minimumTime(int totalCourses, int[][] prerequisites, int[] timeToComplete) {
4 // Create a graph represented as an adjacency list
5 List<Integer>[] graph = new List[totalCourses];
6 Arrays.setAll(graph, k -> new ArrayList<>());
7
8 // Create an array to track the number of prerequisites for each course
9 int[] incomingEdges = new int[totalCourses];
10
11 // Build the graph and count incoming edges for each node (course)
12 for (int[] relation : prerequisites) {
13 // Courses are 1-indexed, but our array/graph is 0-indexed
14 int prerequisite = relation[0] - 1;
15 int course = relation[1] - 1;
16 graph[prerequisite].add(course);
17 ++incomingEdges[course];
18 }
19
20 // Initialize a queue for courses that have no prerequisites
21 Deque<Integer> queue = new ArrayDeque<>();
22 // Array to store the time to finish each course including prerequisites
23 int[] finishTime = new int[totalCourses];
24 // Variable to store the maximum time to finish all courses
25 int maxTime = 0;
26
27 // Enqueue courses without prerequisites and set their finish times
28 for (int i = 0; i < totalCourses; ++i) {
29 if (incomingEdges[i] == 0) {
30 queue.offer(i);
31 finishTime[i] = timeToComplete[i];
32 maxTime = Math.max(maxTime, finishTime[i]);
33 }
34 }
35
36 // Process the courses in topological order
37 while (!queue.isEmpty()) {
38 int currentCourse = queue.pollFirst();
39 // For each course that follows the current one
40 for (int nextCourse : graph[currentCourse]) {
41 // Update the finish time to the maximum of the current known time and the time required after finishing the current course
42 finishTime[nextCourse] = Math.max(finishTime[nextCourse], finishTime[currentCourse] + timeToComplete[nextCourse]);
43 maxTime = Math.max(maxTime, finishTime[nextCourse]);
44 // If the course has no remaining prerequisites, add it to the queue
45 if (--incomingEdges[nextCourse] == 0) {
46 queue.offer(nextCourse);
47 }
48 }
49 }
50
51 // Return the maximum time to finish all courses
52 return maxTime;
53 }
54}
55
1class Solution {
2public:
3 int minimumTime(int n, vector<vector<int>>& relations, vector<vector<int>>& time) {
4 // Create a graph data structure to represent courses and their prerequisites
5 vector<vector<int>> graph(n);
6 // A vector to keep track of the number of prerequisites (in-degree) for each course
7 vector<int> inDegree(n, 0);
8
9 // Construct the graph and fill in-degree data
10 for (const auto& relation : relations) {
11 // Courses are numbered starting 1, so subtract 1 to get a 0-based index
12 int prevCourse = relation[0] - 1;
13 int nextCourse = relation[1] - 1;
14 // Create an edge from 'prevCourse' to 'nextCourse'
15 graph[prevCourse].push_back(nextCourse);
16 // Increment in-degree for the 'nextCourse'
17 ++inDegree[nextCourse];
18 }
19
20 // Queue for BFS traversal
21 queue<int> courseQueue;
22 // Vector to keep track of the total time to complete each course
23 vector<int> finishTime(n, 0);
24 // Initialize the final answer to time completion
25 int totalTime = 0;
26
27 // Enqueue courses with no prerequisites
28 for (int i = 0; i < n; ++i) {
29 if (inDegree[i] == 0) {
30 courseQueue.push(i);
31 finishTime[i] = time[i];
32 // Update total time with the time taken to complete this course
33 totalTime = max(totalTime, time[i]);
34 }
35 }
36
37 // Process courses in the order they can be taken
38 while (!courseQueue.empty()) {
39 int currentCourse = courseQueue.front();
40 courseQueue.pop();
41
42 // Check all the next courses that can be taken after the current course
43 for (int nextCourse : graph[currentCourse]) {
44 // Decrease the in-degree of the next course
45 --inDegree[nextCourse];
46
47 // If all prerequisites of the next course have been taken, add to queue
48 if (inDegree[nextCourse] == 0) {
49 courseQueue.push(nextCourse);
50 }
51
52 // Update the finish time of the next course
53 // It will be the maximum of its current finish time and
54 // the finish time of its prerequisite (current course) plus its own duration
55 finishTime[nextCourse] = max(finishTime[nextCourse], finishTime[currentCourse] + time[nextCourse]);
56 // Update the total time completion with the updated finish time of the next course
57 totalTime = max(totalTime, finishTime[nextCourse]);
58 }
59 }
60
61 // Return the maximum time required to finish all courses
62 return totalTime;
63 }
64};
65
1function minimumTime(numCourses: number, prerequisites: number[][], courseDurations: number[]): number {
2 // Graph represented as an adjacency list
3 const graph: number[][] = Array(numCourses)
4 .fill(0)
5 .map(() => []);
6
7 // Array to keep track of incoming edges (in-degree) for each node
8 const inDegrees: number[] = Array(numCourses).fill(0);
9
10 // Build graph and populate inDegrees array
11 for(const [source, target] of prerequisites) {
12 graph[source - 1].push(target - 1);
13 ++inDegrees[target - 1];
14 }
15
16 // Queue for processing courses that have no prerequisites or whose prerequisites have been completed
17 const queue: number[] = [];
18
19 // Array to keep the completion time for each course
20 const finishTimes: number[] = Array(numCourses).fill(0);
21
22 // Variable to keep track of the maximum time required to finish all courses
23 let maxTime: number = 0;
24
25 // Initialize the queue with courses that have no prerequisites and calculate their finish times
26 for(let i = 0; i < numCourses; ++i) {
27 if(inDegrees[i] === 0) {
28 queue.push(i);
29 finishTimes[i] = courseDurations[i];
30 maxTime = Math.max(maxTime, finishTimes[i]);
31 }
32 }
33
34 // Process courses in topological order
35 while(queue.length > 0) {
36 const currentCourse = queue.shift()!;
37 for(const nextCourse of graph[currentCourse]) {
38 finishTimes[nextCourse] = Math.max(finishTimes[nextCourse], finishTimes[currentCourse] + courseDurations[nextCourse]);
39 maxTime = Math.max(maxTime, finishTimes[nextCourse]);
40 // When a prerequisite course is completed, decrease in-degree of the next course
41 if (--inDegrees[nextCourse] === 0) {
42 queue.push(nextCourse);
43 }
44 }
45 }
46
47 // Return the maximum time to complete all courses
48 return maxTime;
49}
50
Time and Space Complexity
The time complexity of the given code is O(V + E)
, where V
is the number of courses (nodes) and E
is the number of dependencies (edges). This complexity arises because each course is enqueued and dequeued exactly once, which is O(V)
. Every dependency is looked at exactly once when iterating through the adjacency list, which gives O(E)
. Therefore, the total is O(V + E)
.
The space complexity is also O(V + E)
because we need to store the graph g
, which contains E
edges, the indeg
array of size V
, and the f
array of size V
. Considering the queue's space, in the worst case, it could hold all vertices, which adds up to O(V)
. However, since this does not change the overall space complexity, it remains O(V + E)
.
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Topological Sort Topological Order Prereq Breadth First Search Review problems graph_bfs Directed Graph Before we get started on topological order let's talk about directed graphs first A graph is directed when its edges have directions these edges are also called arcs Suppose that v w are vertices in a directed
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Want a Structured Path to Master System Design Too? Donāt Miss This!