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.
#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.