The LeetCode problem Parallel Courses II is about scheduling courses given prerequisite constraints and a limit on how many courses you can take per semester.
You are given:
n, representing the total number of courses labeled from 1 to n.prerequisites where each element is a pair [xi, yi] meaning course xi must be taken before course yi.k, the maximum number of courses you can take in any single semester.
The goal is to determine the minimum number of semesters required to complete all n courses, given the prerequisite relationships and the per-semester course limit.
Constraints:
k courses that have no unmet prerequisites.
At first glance, this problem seems similar to topological sorting or finding the order of courses to satisfy prerequisites. However, the twist is the limit k on the number of courses per semester.
A brute-force approach would consider all possible combinations of courses to take each semester, but this quickly becomes infeasible as the number of courses grows (since there are 2n subsets).
We need to optimize by:
k available courses each time.k), and avoid revisiting states that have already been reached in fewer semesters.
We'll use a BFS (Breadth-First Search) or DP with bitmasking to represent the state of courses taken. Here's how the solution works:
n, where the i-th bit is 1 if course i is completed.
k to represent all possible choices for the next semester.
This approach ensures that we always find the minimal number of semesters, and the use of bitmasks and BFS keeps the solution efficient for the given constraints.
Example:
n = 4, prerequisites = [[2,1],[3,1],[1,4]], k = 2
Step 1: Build prerequisite mapping:
Step 2: Initial state: no courses taken (mask = 0000).
Available courses: 2 and 3 (no prerequisites).
Choices this semester: Take 2, take 3, or take both (since k=2).
Best choice: Take both 2 and 3 (mask = 1100).
Step 3: Next semester, available courses:
mask = 1110).
Step 4: Next semester, available courses:
mask = 1111).
All courses are completed in 3 semesters.
Brute-force approach:
n (i.e., O(n!)).k can be up to O(2^k), but since k is small (≤ n), this is manageable.
This is feasible for n ≤ 15 (as per problem constraints).
The key to solving "Parallel Courses II" efficiently is to model the course-taking process as a state-space problem using bitmasking, and to use BFS or DP to find the minimal number of semesters. By keeping track of which courses are completed and which are available, and by only considering valid subsets of courses per semester, we avoid redundant work and ensure an optimal solution. This approach is both elegant and practical for the problem's constraints.
from collections import deque
from itertools import combinations
class Solution:
def minNumberOfSemesters(self, n, dependencies, k):
prereq = [0] * n
for u, v in dependencies:
prereq[v-1] |= 1 << (u-1)
queue = deque()
visited = set()
queue.append((0, 0)) # (bitmask, semester count)
visited.add(0)
full_mask = (1 << n) - 1
while queue:
mask, semester = queue.popleft()
if mask == full_mask:
return semester
# Find available courses
available = []
for i in range(n):
if not (mask & (1 << i)) and (prereq[i] & mask) == prereq[i]:
available.append(i)
# Generate all subsets of available courses up to k
for courses in combinations(available, min(k, len(available))):
next_mask = mask
for c in courses:
next_mask |= (1 << c)
if next_mask not in visited:
visited.add(next_mask)
queue.append((next_mask, semester + 1))
# If less than k courses available, can take all at once
if len(available) <= k:
next_mask = mask
for c in available:
next_mask |= (1 << c)
if next_mask not in visited:
visited.add(next_mask)
queue.append((next_mask, semester + 1))
#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm>
using namespace std;
class Solution {
public:
int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {
vector<int> prereq(n, 0);
for (const auto& dep : dependencies) {
prereq[dep[1]-1] |= 1 << (dep[0]-1);
}
queue<pair<int, int>> q;
unordered_set<int> visited;
q.push({0, 0});
visited.insert(0);
int full_mask = (1 << n) - 1;
while (!q.empty()) {
auto [mask, semester] = q.front(); q.pop();
if (mask == full_mask) return semester;
vector<int> available;
for (int i = 0; i < n; ++i) {
if (!(mask & (1 << i)) && (prereq[i] & mask) == prereq[i]) {
available.push_back(i);
}
}
int sz = available.size();
vector<int> idx(sz);
for (int i = 0; i < sz; ++i) idx[i] = i;
// Generate all combinations up to k
for (int take = 1; take <= min(k, sz); ++take) {
vector<bool> select(sz, false);
fill(select.end()-take, select.end(), true);
do {
int next_mask = mask;
for (int i = 0; i < sz; ++i)
if (select[i]) next_mask |= (1 << available[i]);
if (!visited.count(next_mask)) {
visited.insert(next_mask);
q.push({next_mask, semester+1});
}
} while (next_permutation(select.begin(), select.end()));
}
// If sz <= k, can take all
if (sz <= k) {
int next_mask = mask;
for (int c : available) next_mask |= (1 << c);
if (!visited.count(next_mask)) {
visited.insert(next_mask);
q.push({next_mask, semester+1});
}
}
}
return -1;
}
};
import java.util.*;
class Solution {
public int minNumberOfSemesters(int n, int[][] dependencies, int k) {
int[] prereq = new int[n];
for (int[] dep : dependencies) {
prereq[dep[1]-1] |= 1 << (dep[0]-1);
}
Queue<int[]> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.add(new int[]{0, 0});
visited.add(0);
int fullMask = (1 << n) - 1;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int mask = curr[0], semester = curr[1];
if (mask == fullMask) return semester;
List<Integer> available = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) == 0 && (prereq[i] & mask) == prereq[i]) {
available.add(i);
}
}
int sz = available.size();
// Generate all combinations up to k
for (int take = 1; take <= Math.min(k, sz); ++take) {
combination(queue, visited, mask, available, semester, take);
}
// If sz <= k, can take all
if (sz <= k) {
int nextMask = mask;
for (int c : available) nextMask |= (1 << c);
if (!visited.contains(nextMask)) {
visited.add(nextMask);
queue.add(new int[]{nextMask, semester+1});
}
}
}
return -1;
}
private void combination(Queue<int[]> queue, Set<Integer> visited, int mask, List<Integer> available, int semester, int k) {
combinationHelper(queue, visited, mask, available, semester, k, 0, 0);
}
private void combinationHelper(Queue<int[]> queue, Set<Integer> visited, int mask, List<Integer> available, int semester, int k, int start, int currMask) {
if (k == 0) {
int nextMask = mask | currMask;
if (!visited.contains(nextMask)) {
visited.add(nextMask);
queue.add(new int[]{nextMask, semester+1});
}
return;
}
for (int i = start; i < available.size(); ++i) {
combinationHelper(queue, visited, mask, available, semester, k-1, i+1, currMask | (1 << available.get(i)));
}
}
}
/**
* @param {number} n
* @param {number[][]} dependencies
* @param {number} k
* @return {number}
*/
var minNumberOfSemesters = function(n, dependencies, k) {
let prereq = new Array(n).fill(0);
for (let [u, v] of dependencies) {
prereq[v-1] |= 1 << (u-1);
}
let queue = [[0, 0]];
let visited = new Set();
visited.add(0);
let fullMask = (1 << n) - 1;
while (queue.length > 0) {
let [mask, semester] = queue.shift();
if (mask === fullMask) return semester;
let available = [];
for (let i = 0; i < n; ++i) {
if (((mask >> i) & 1) === 0 && (prereq[i] & mask) === prereq[i]) {
available.push(i);
}
}
let sz = available.length;
// Helper to generate all combinations
function combine(arr, k, start, curr, res) {
if (curr.length === k) {
res.push([...curr]);
return;
}
for (let i = start; i < arr.length; ++i) {
curr.push(arr[i]);
combine(arr, k, i+1, curr, res);
curr.pop();
}
}
for (let take = 1; take <= Math.min(k, sz); ++take) {
let combos = [];
combine(available, take, 0, [], combos);
for (let combo of combos) {
let nextMask = mask;
for (let c of combo) {
nextMask |= (1 << c);
}
if (!visited.has(nextMask)) {
visited.add(nextMask);
queue.push([nextMask, semester+1]);
}
}
}
if (sz <= k) {
let nextMask = mask;
for (let c of available) nextMask |= (1 << c);
if (!visited.has(nextMask)) {
visited.add(nextMask);
queue.push([nextMask, semester+1]);
}
}
}
return -1;
};