In this guide, you will get 1494. Parallel Courses II LeetCode Solution with the best time and space complexity. The solution to Parallel Courses II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given an array relations where relations[i] = [prevCoursei, nextCoursei], representing a prerequisite relationship between course prevCoursei and course nextCoursei: course prevCoursei has to be taken before course nextCoursei. Also, you are given the integer k.
In one semester, you can take at most k courses as long as you have taken all the prerequisites in the previous semesters for the courses you are taking.
Return the minimum number of semesters needed to take all courses. The testcases will be generated such that it is possible to take every course.
Example 1:
Input: n = 4, relations = [[2,1],[3,1],[1,4]], k = 2
Output: 3
Explanation: The figure above represents the given graph.
In the first semester, you can take courses 2 and 3.
In the second semester, you can take course 1.
In the third semester, you can take course 4.
Example 2:
Input: n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2
Output: 4
Explanation: The figure above represents the given graph.
In the first semester, you can only take courses 2 and 3 since you cannot take more than two per semester.
In the second semester, you can take course 4.
In the third semester, you can take course 1.
In the fourth semester, you can take course 5.
1 <= n <= 15
1 <= k <= n
0 <= relations.length <= n * (n-1) / 2
relations[i].length == 2
1 <= prevCoursei, nextCoursei <= n
prevCoursei != nextCoursei
All the pairs [prevCoursei, nextCoursei] are unique.
The given graph is a directed acyclic graph.
Complexity Analysis
Time Complexity: O(2^n \cdot n)
Space Complexity: O(2^n)
1494. Parallel Courses II LeetCode Solution in C++
class Solution {
public:
int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
// dp[i] := the minimum number of semesters to take the courses, where i is
// the bitmask of the taken courses
vector<int> dp(1 << n, n);
// prereq[i] := the bitmask of all the dependencies of the i-th course
vector<int> prereq(n);
for (const vector<int>& relation : relations) {
const int prevCourse = relation[0] - 1;
const int nextCourse = relation[1] - 1;
prereq[nextCourse] |= 1 << prevCourse;
}
dp[0] = 0; // Don't need time to finish 0 course.
for (int i = 0; i < dp.size(); ++i) {
// the bitmask of all the courses can be taken
int coursesCanBeTaken = 0;
// Can take the j-th course if i contains all of j's prerequisites.
for (int j = 0; j < n; ++j)
if ((i & prereq[j]) == prereq[j])
coursesCanBeTaken |= 1 << j;
// Don't take any course which is already taken.
// (i represents set of courses that are already taken)
coursesCanBeTaken &= ~i;
// Enumerate every bitmask subset of `coursesCanBeTaken`.
for (unsigned s = coursesCanBeTaken; s > 0;
s = (s - 1) & coursesCanBeTaken)
if (popcount(s) <= k)
// Any combination of courses (if <= k) can be taken now.
// i | s := combining courses taken with courses can be taken.
dp[i | s] = min(dp[i | s], dp[i] + 1);
}
return dp.back();
}
}; /* code provided by PROGIEZ */
1494. Parallel Courses II LeetCode Solution in Java
class Solution {
public int minNumberOfSemesters(int n, int[][] relations, int k) {
// dp[i] := the minimum number of semesters to take the courses, where i is
// the bitmask of the taken courses
int[] dp = new int[1 << n];
Arrays.fill(dp, n);
// prereq[i] := the bitmask of all the dependencies of the i-th course
int[] prereq = new int[n];
for (int[] r : relations) {
final int prevCourse = r[0] - 1;
final int nextCourse = r[1] - 1;
prereq[nextCourse] |= 1 << prevCourse;
}
dp[0] = 0; // Don't need time to finish 0 course.
for (int i = 0; i < dp.size(); ++i) {
// the bitmask of all the courses can be taken
int coursesCanBeTaken = 0;
// Can take the j-th course if i contains all of j's prerequisites.
for (int j = 0; j < n; ++j)
if ((i & prereq[j]) == prereq[j])
coursesCanBeTaken |= 1 << j;
// Don't take any course which is already taken.
// (i represents set of courses that are already taken)
coursesCanBeTaken &= ~i;
// Enumerate every bitmask subset of `coursesCanBeTaken`.
for (int s = coursesCanBeTaken; s > 0; s = (s - 1) & coursesCanBeTaken)
if (Integer.bitCount(s) <= k)
// Any combination of courses (if <= k) can be taken now.
// i | s := combining courses taken with courses can be taken.
dp[i | s] = Math.min(dp[i | s], dp[i] + 1);
}
return dp[(1 << n) - 1];
}
} // code provided by PROGIEZ
1494. Parallel Courses II LeetCode Solution in Python
class Solution:
def minNumberOfSemesters(
self,
n: int,
relations: list[list[int]],
k: int,
) -> int:
# dp[i] := the minimum number of semesters to take the courses, where i is
# the bitmask of the taken courses
dp = [n] * (1 << n)
# prereq[i] := bitmask of all dependencies of course i
prereq = [0] * n
for prevCourse, nextCourse in relations:
prereq[nextCourse - 1] |= 1 << prevCourse - 1
dp[0] = 0 # Don't need time to finish 0 course.
for i in range(1 << n):
# the bitmask of all the courses can be taken
coursesCanBeTaken = 0
# Can take the j-th course if i contains all of j's prerequisites.
for j in range(n):
if (i & prereq[j]) == prereq[j]:
coursesCanBeTaken |= 1 << j
# Don't take any course which is already taken.
# (i represents set of courses that are already taken)
coursesCanBeTaken &= ~i
# Enumerate every bitmask subset of `coursesCanBeTaken`.
s = coursesCanBeTaken
while s:
if s.bit_count() <= k:
# Any combination of courses (if <= k) can be taken now.
# i | s := combining courses taken with courses can be taken.
dp[i | s] = min(dp[i | s], dp[i] + 1)
s = (s - 1) & coursesCanBeTaken
return dp[-1] # code by PROGIEZ
