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```java
2import java.util.*;
3
4public class ParallelCourses {
5 public static int minTime(int n,
```The Java solution builds upon creating adjacency lists using arrays of lists, maintaining indegree counts to help with topological sorting, then using a queue to track courses with no prerequisites. After processing all courses, it calculates the required maximum completion time.
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.