You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCoursej, nextCoursej] denotes that course prevCoursej has to be completed before course nextCoursej (prerequisite relationship). Furthermore, you are given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)th course.
You must find the minimum number of months needed to complete all the courses following these rules:
Return the minimum number of months needed to complete all the courses.
Note: The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).
Example 1:
Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5] Output: 8 Explanation: The figure above represents the given graph and the time required to complete each course. We start course 1 and course 2 simultaneously at month 0. Course 1 takes 3 months and course 2 takes 2 months to complete respectively. Thus, the earliest time we can start course 3 is at month 3, and the total time required is 3 + 5 = 8 months.
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: The figure above represents the given graph and the time required to complete each course. You can start courses 1, 2, and 3 at month 0. You can complete them after 1, 2, and 3 months respectively. Course 4 can be taken only after course 3 is completed, i.e., after 3 months. It is completed after 3 + 4 = 7 months. Course 5 can be taken only after courses 1, 2, 3, and 4 have been completed, i.e., after max(1,2,3,7) = 7 months. Thus, the minimum time needed to complete all the courses is 7 + 5 = 12 months.
Constraints:
1 <= n <= 5 * 1040 <= relations.length <= min(n * (n - 1) / 2, 5 * 104)relations[j].length == 21 <= prevCoursej, nextCoursej <= nprevCoursej != nextCoursej[prevCoursej, nextCoursej] are unique.time.length == n1 <= time[i] <= 104The key idea in #2050 Parallel Courses III is to model courses and their prerequisite relationships as a directed acyclic graph (DAG). Each node represents a course, and edges indicate prerequisite dependencies. Since multiple courses can run in parallel, the goal is not just ordering but finding the maximum time along prerequisite paths.
A common strategy is to use Topological Sort (typically with Kahn's Algorithm) combined with dynamic programming. Maintain an array where dp[i] represents the earliest time course i can be completed. When processing nodes in topological order, update dependent courses by taking the maximum completion time among their prerequisites and adding the current course duration.
This effectively computes the longest path in a DAG, which represents the minimum total time required to finish all courses when parallel execution is allowed. The graph traversal ensures each node and edge is processed efficiently.
The approach runs in linear time relative to the number of courses and relations, making it scalable for large graphs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Topological Sort with DP (Longest Path in DAG) | O(V + E) | O(V + E) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
What is the earliest time a course can be taken?
How would you solve the problem if all courses take equal time?
How would you generalize this approach?
This approach involves topologically sorting the courses based on their prerequisites and then calculating the minimal time to complete each course using dynamic programming.
(a,b) is a directed edge from a to b.Time Complexity: O(n + E), where n is the number of courses and E is the number of prerequisite relationships, due to traversing all nodes and edges once.
Space Complexity: O(n + E), needed to store the graph and additional arrays.
1```python
2def minTime(n, relations, time):
3 from collections import deque, defaultdict
4
5 adj = defaultdict(list
```This Python solution uses collections to define adjacency lists and maintains indegrees for each node. It efficiently processes courses using a deque for queue operations and updates the time required using a dp array, finally finding the maximum time needed to complete all courses.
This approach uses Depth-First Search (DFS) with memorization to efficiently compute the completion time for courses.
Time Complexity: O(n + E), visiting each node and edge at least once.
Space Complexity: O(n + E), due to storage for graph data and function call stack.
```Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems involving topological sorting, DAG processing, and longest-path style dynamic programming are common in FAANG-style interviews. Parallel Courses III is considered a strong practice problem for mastering these concepts.
The optimal approach models the courses as a directed acyclic graph and applies topological sorting with dynamic programming. By computing the longest completion time from prerequisites for each course, we determine the minimum time needed to finish all courses while allowing parallel execution.
Topological sort ensures courses are processed only after all prerequisites are completed. This ordering allows us to correctly propagate the maximum completion time from prerequisite courses to dependent courses.
Adjacency lists are commonly used to represent the course dependency graph efficiently. A queue is used for Kahn's topological sort, while an array tracks the earliest completion time for each course during the dynamic programming updates.
The Java solution conducts DFS to determine each course's minimal completion time, storing the results in a dp array to speed up computations. Using this technique, we can compute the maximum time needed to complete all courses efficiently.