Parallel Courses II — Solution in Python, Java & C++
Parallel Courses II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Parallel Courses II is a hard coding problem on dynamic programming, bit manipulation and graph, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Bit Manipulation, Graph, Bitmask
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n courses labelled 1 to n. Each entry relations[i] = [prevCourse, nextCourse] says that prevCourse must be completed before nextCourse can be taken. The prerequisites form no cycle.
In one semester you may take at most k courses, provided every prerequisite of each of them was completed in an earlier semester.
Return the minimum number of semesters needed to take all the courses.
Example 1
Input: n = 5, relations = [[1,3],[2,3],[3,4],[3,5]], k = 2
Output: 3
Explanation: Courses 1 and 2, then 3, then 4 and 5.
Example 2
Input: n = 3, relations = [], k = 2
Output: 2
Example 3
Input: n = 4, relations = [[1,2],[2,3],[3,4]], k = 4
Output: 4
Explanation: A chain allows only one course per semester.
Constraints
1 <= n <= 151 <= k <= n0 <= relations.length <= n * (n-1) / 2relations[i].length == 21 <= prevCourse, nextCourse <= nprevCourse != nextCourseAll pairs are distinctThe prerequisite graph is acyclic
Hints for Parallel Courses II
Hint 1
Picking the available courses greedily (for example by how many courses depend on them) fails on some graphs — this needs an exact search.
Hint 2
With n <= 15, the set of completed courses is a bitmask. From a mask, the courses you may take next are those whose prerequisite mask is contained in it.
Hint 3
Let
dp[mask]be the fewest semesters to completemask. If at mostkcourses are available, take them all; otherwise try everyk-subset of the available ones (enumerate submasks).
How to solve Parallel Courses II
The state is the set of finished courses, a 15-bit mask. From each state either all available courses fit into one semester, or we must choose exactly k of them — and trying every such choice by submask enumeration is affordable.
Approach
- Compute
pre[c], the mask of prerequisites of coursec. - Set
dp[0] = 0and everything else to infinity; visit masks in increasing order. - For a reachable
mask, letavailbe the courses outsidemaskwhosepreis inside it. - If
popcount(avail) <= k, relaxdp[mask | avail]withdp[mask] + 1. Otherwise enumerate the submaskssubofavailwith exactlykbits and relaxdp[mask | sub]. - Return
dp[2^n - 1].
Why it works
Taking an available course now never hurts: it can only unlock more courses later. So when everything available fits, taking all of it is optimal, and when it does not fit, an optimal schedule fills the semester with exactly k available courses — all of which the enumeration tries. Transitions only add courses, so increasing numeric order handles every mask after its predecessors.
Complexity
- Time —
O(3^n) in the worst case (submask enumeration) - Space —
O(2^n)
Pitfalls
- Greedy by depth, out-degree or topological order is wrong — it was the accepted-then-broken approach for this problem.
- Courses are 1-indexed in
relations; shift them to bits0..n-1. - When more than
kcourses are available, a semester with fewer thankcourses is never needed, so onlyk-subsets must be tried.
Reference solution
Python
from typing import List
def minNumberOfSemesters(n: int, relations: List[List[int]], k: int) -> int:
pre = [0] * n
for a, b in relations:
pre[b - 1] |= 1 << (a - 1)
full = 1 << n
inf = float("inf")
dp = [inf] * full
dp[0] = 0
for mask in range(full):
if dp[mask] == inf:
continue
avail = 0
for c in range(n):
if not (mask >> c) & 1 and (pre[c] & mask) == pre[c]:
avail |= 1 << c
if avail == 0:
continue
nxt = dp[mask] + 1
if bin(avail).count("1") <= k:
if nxt < dp[mask | avail]:
dp[mask | avail] = nxt
else:
sub = avail
while sub:
if bin(sub).count("1") == k and nxt < dp[mask | sub]:
dp[mask | sub] = nxt
sub = (sub - 1) & avail
return dp[full - 1]Java
public static int minNumberOfSemesters(int n, int[][] relations, int k) {
int[] pre = new int[n];
for (int[] r : relations) pre[r[1] - 1] |= 1 << (r[0] - 1);
int full = 1 << n, INF = 1 << 30;
int[] dp = new int[full];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int mask = 0; mask < full; mask++) {
if (dp[mask] == INF) continue;
int avail = 0;
for (int c = 0; c < n; c++) {
if ((mask & (1 << c)) == 0 && (pre[c] & mask) == pre[c]) avail |= 1 << c;
}
if (avail == 0) continue;
int nxt = dp[mask] + 1;
if (Integer.bitCount(avail) <= k) {
dp[mask | avail] = Math.min(dp[mask | avail], nxt);
} else {
for (int sub = avail; sub != 0; sub = (sub - 1) & avail) {
if (Integer.bitCount(sub) == k) dp[mask | sub] = Math.min(dp[mask | sub], nxt);
}
}
}
return dp[full - 1];
}C++
int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
vector<int> pre(n, 0);
for (auto& r : relations) pre[r[1] - 1] |= 1 << (r[0] - 1);
int full = 1 << n, INF = 1 << 30;
vector<int> dp(full, INF);
dp[0] = 0;
for (int mask = 0; mask < full; mask++) {
if (dp[mask] == INF) continue;
int avail = 0;
for (int c = 0; c < n; c++) {
if (!(mask & (1 << c)) && (pre[c] & mask) == pre[c]) avail |= 1 << c;
}
if (avail == 0) continue;
int nxt = dp[mask] + 1;
if (__builtin_popcount(avail) <= k) {
dp[mask | avail] = min(dp[mask | avail], nxt);
} else {
for (int sub = avail; sub; sub = (sub - 1) & avail) {
if (__builtin_popcount(sub) == k) dp[mask | sub] = min(dp[mask | sub], nxt);
}
}
}
return dp[full - 1];
}JavaScript
var minNumberOfSemesters = function(n, relations, k) {
var pre = new Array(n).fill(0);
for (var i = 0; i < relations.length; i++) pre[relations[i][1] - 1] |= 1 << (relations[i][0] - 1);
var full = 1 << n, INF = 1 << 30;
var dp = new Array(full).fill(INF);
dp[0] = 0;
var pop = function(x) { var c = 0; while (x) { c += x & 1; x >>= 1; } return c; };
for (var mask = 0; mask < full; mask++) {
if (dp[mask] === INF) continue;
var avail = 0;
for (var c = 0; c < n; c++) {
if (!(mask & (1 << c)) && (pre[c] & mask) === pre[c]) avail |= 1 << c;
}
if (avail === 0) continue;
var nxt = dp[mask] + 1;
if (pop(avail) <= k) {
if (nxt < dp[mask | avail]) dp[mask | avail] = nxt;
} else {
for (var sub = avail; sub; sub = (sub - 1) & avail) {
if (pop(sub) === k && nxt < dp[mask | sub]) dp[mask | sub] = nxt;
}
}
}
return dp[full - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Bit Manipulation