
Sponsored
Sponsored
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```javascript
2function minTime(n, relations, time) {
3 const indegree = new Array(n + 1).fill(0);
4 const adj = Array.from({ length: n + 1 }, () => []);
5 const dp = new Array(n + 1).fill(0);
6
7 for (const [u, v] of relations) {
8 adj[u].push(v);
9 indegree[v]++;
This JavaScript implementation constructs an adjacency list and degrees array to use in topological sorting. By processing with a queue, it determines course completion order, updating a `dp` to store the minimum computation times and ultimately derives the result as the maximum time needed.
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.
using System;
using System.Collections.Generic;
public class ParallelCoursesDFS {
private static int DFS(int u, List<int>[] adj, int[] dp, int[] time) {
if (dp[u] != 0) return dp[u];
dp[u] = time[u - 1];
foreach (var v in adj[u]) {
dp[u] = Math.Max(dp[u], DFS(v, adj, dp, time) + time[u - 1]);
}
return dp[u];
}
public static int MinTimeDFS(int n, int[][] relations, int[] time) {
List<int>[] adj = new List<int>[n + 1];
for (int i = 0; i <= n; i++)
adj[i] = new List<int>();
foreach (var relation in relations)
adj[relation[0]].Add(relation[1]);
int[] dp = new int[n + 1];
int maxTime = 0;
for (int i = 1; i <= n; i++)
maxTime = Math.Max(maxTime, DFS(i, adj, dp, time));
return maxTime;
}
public static void Main() {
int n = 5;
int[][] relations = new int[][] { new int[] { 1,5 }, new int[] { 2,5 }, new int[] { 3,5 }, new int[] { 3,4 }, new int[] { 4,5 } };
int[] time = new int[] { 1, 2, 3, 4, 5 };
Console.WriteLine(MinTimeDFS(n, relations, time));
}
}
```The C# solution implements DFS with memorization, storing the results in the dp array to optimize course time analysis. Each course is processed with respect to its prerequisites using recursion and stored results expedite the overall solution.