Parallel Courses II

Hard
1343.

Parallel Courses II

Parallel Courses II is a hard coding problem on dynamic programming, bit manipulation and graph, asked in Amazon and Google interviews.

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 <= 15
  • 1 <= k <= n
  • 0 <= relations.length <= n * (n-1) / 2
  • relations[i].length == 2
  • 1 <= prevCourse, nextCourse <= n
  • prevCourse != nextCourse
  • All pairs are distinct
  • The prerequisite graph is acyclic
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} relations
 * @param {number} k
 * @return {number}
 */
var minNumberOfSemesters = function(n, relations, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 15
  • 1 <= k <= n
  • 0 <= relations.length <= n * (n-1) / 2
  • relations[i].length == 2
  • 1 <= prevCourse, nextCourse <= n
  • prevCourse != nextCourse
  • All pairs are distinct
  • The prerequisite graph is acyclic

Hints for Parallel Courses II

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

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

  3. Hint 3

    Let dp[mask] be the fewest semesters to complete mask. If at most k courses are available, take them all; otherwise try every k-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

  1. Compute pre[c], the mask of prerequisites of course c.
  2. Set dp[0] = 0 and everything else to infinity; visit masks in increasing order.
  3. For a reachable mask, let avail be the courses outside mask whose pre is inside it.
  4. If popcount(avail) <= k, relax dp[mask | avail] with dp[mask] + 1. Otherwise enumerate the submasks sub of avail with exactly k bits and relax dp[mask | sub].
  5. 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 bits 0..n-1.
  • When more than k courses are available, a semester with fewer than k courses is never needed, so only k-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