LeetCode 1494: Parallel Courses II
Problem Description
Explanation:
To solve this problem, we can use a topological sorting algorithm combined with dynamic programming. We will first construct the prerequisite graph from the given relations and then perform a topological sort to determine the order in which the courses can be taken. We will use dynamic programming to calculate the minimum number of semesters needed to take all courses.
- Construct the prerequisite graph from the given relations.
- Perform topological sorting to get the order in which courses can be taken.
- Use dynamic programming to calculate the minimum number of semesters needed to take all courses.
Time Complexity: O(n * 2^n) Space Complexity: O(2^n)
:
Solutions
class Solution {
public int minNumberOfSemesters(int n, int[][] relations, int k) {
int[] pre = new int[n];
for (int[] relation : relations) {
pre[relation[1] - 1] |= 1 << (relation[0] - 1);
}
int[] dp = new int[1 << n];
Arrays.fill(dp, n);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
int canTake = 0;
for (int i = 0; i < n; i++) {
if ((mask & pre[i]) == pre[i] && (mask & (1 << i)) == 0) {
canTake |= 1 << i;
}
}
for (int sub = canTake; sub > 0; sub = (sub - 1) & canTake) {
if (Integer.bitCount(sub) <= k) {
dp[mask | sub] = Math.min(dp[mask | sub], dp[mask] + 1);
}
}
}
return dp[(1 << n) - 1];
}
}Loading editor...