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] <= 104This 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.This C solution initializes adjacency lists for the graph and an array for in-degrees. The courses are processed based on their prerequisites using a queue (to implement the topological sort). The dp array keeps track of the minimum time to finish each course as the prerequisites are progressively met. The total time to complete all courses becomes the maximum value in the dp array.
C++
Java
Python
C#
JavaScript
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.
This approach uses Depth-First Search (DFS) with memorization to efficiently compute the completion time for courses.
This C implementation makes use of a recursive DFS function to calculate the minimum completion time for each course by traversing through its dependencies. Memorization is utilized to store the time taken to complete each course dp[u], thus optimizing the solution by preventing recalculations.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Topological Sort with Dynamic Programming | 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. |
| DFS with Memorization | Time Complexity: O(n + E), visiting each node and edge at least once. |
Parallel Courses III - Leetcode 2050 - Python • NeetCodeIO • 17,400 views views
Watch 9 more video solutions →Practice Parallel Courses III with our built-in code editor and test cases.
Practice on FleetCode