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.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dfs(int u, const vector<vector<int>>& adj, vector<int>& dp, const vector<int>& time) {
if (dp[u] != 0) return dp[u];
dp[u] = time[u - 1];
for (int v : adj[u]) {
dp[u] = max(dp[u], dfs(v, adj, dp, time) + time[u - 1]);
}
return dp[u];
}
int minTimeDFS(int n, vector<vector<int>>& relations, vector<int>& time) {
vector<vector<int>> adj(n + 1);
for (const auto& rel : relations) {
adj[rel[0]].push_back(rel[1]);
}
vector<int> dp(n + 1, 0);
int maxTime = 0;
for (int i = 1; i <= n; ++i) {
maxTime = max(maxTime, dfs(i, adj, dp, time));
}
return maxTime;
}
int main() {
int n = 5;
vector<vector<int>> relations = {{1,5},{2,5},{3,5},{3,4},{4,5}};
vector<int> time = {1, 2, 3, 4, 5};
cout << minTimeDFS(n, relations, time) << endl;
return 0;
}
```This C++ approach executes a DFS for each course, using a memorization array dp to store and calculate the required minimum completion time, preventing redundant computations via already stored results.