LeetCode 1494 - Parallel Courses II

The problem asks us to determine the minimum number of semesters required to complete n courses when there are prerequis

leetcodeharddynamic-programmingbit-manipulationgraph-theorybitmask

LeetCode Problem 1494

Difficulty: 🔴 Hard
Topics: Dynamic Programming, Bit Manipulation, Graph Theory, Bitmask

Solution

Problem Understanding

The problem asks us to determine the minimum number of semesters required to complete n courses when there are prerequisite constraints between some courses and a limit k on the number of courses that can be taken in a single semester. The input consists of an integer n, a list of prerequisite relations relations, and the integer k. Each relation [a, b] indicates that course a must be completed before course b.

The goal is to schedule the courses across semesters such that all prerequisites are satisfied and no semester has more than k courses, returning the minimum number of semesters needed.

The constraints tell us that n is small (<= 15), which hints that bit manipulation and DP over subsets can be used. The relations form a directed acyclic graph (DAG), so there are no cycles and a valid course order exists. Important edge cases include when k is equal to n (all courses could be taken in one semester if prerequisites allow), when relations is empty (all courses are independent), or when some courses have many prerequisites.

Approaches

Brute Force Approach

A naive approach is to generate all permutations of the courses and check which permutations satisfy the prerequisites, then split valid permutations into semesters respecting the k limit. This guarantees correctness because it explores all possible orders. However, this is exponentially slow: there are n! permutations and n can be 15, so it is computationally infeasible. Even pruning based on prerequisites is insufficient due to combinatorial explosion.

Optimal Approach

The optimal approach uses bitmask dynamic programming. Each state is represented by a bitmask mask where the i-th bit is 1 if course i+1 is completed. We also store the minimum number of semesters to reach that state. At each step, we can consider which courses are available to take (all prerequisites completed) and choose subsets of these courses of size up to k to take in the current semester. We update the DP table with the new bitmask state and increment the semester count.

Key observations:

  1. Using bitmask DP is feasible because n <= 15, so there are 2^15 = 32768 possible states.
  2. Prerequisites can be encoded as bitmasks for fast checks: a course is available if all bits corresponding to its prerequisites are set in the current state.
  3. Enumerating subsets of size up to k can be done efficiently with standard bit manipulation techniques.
Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Generates all permutations of courses, checks prerequisites, infeasible for n=15
Bitmask DP O(3^n) O(2^n) Uses bitmask for states, efficiently enumerates available courses each semester

Algorithm Walkthrough

  1. Encode prerequisites: Build an array pre of length n where pre[i] is a bitmask of courses that must be completed before course i.
  2. Initialize DP table: Create an array dp of size 2^n, where dp[mask] is the minimum semesters to reach mask. Set dp[0] = 0 as the base case (no courses taken).
  3. Iterate over states: For each mask from 0 to 2^n - 1, determine which courses are available to take by checking if all prerequisites are satisfied. Available courses form a bitmask avail.
  4. Enumerate subsets of available courses: Generate all subsets of avail of size at most k. For each subset, compute the new mask as next_mask = mask | subset and update dp[next_mask] = min(dp[next_mask], dp[mask] + 1).
  5. Return result: The answer is dp[(1 << n) - 1], the minimum semesters needed to complete all courses.

Why it works: Each DP state encodes exactly which courses have been completed, and transitions consider all valid course combinations up to k courses. By iterating over all states and subsets, the algorithm guarantees that every valid schedule is considered, and the minimum semester count is found.

Python Solution

from typing import List
from itertools import combinations

class Solution:
    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:
        pre = [0] * n
        for u, v in relations:
            pre[v - 1] |= 1 << (u - 1)
        
        size = 1 << n
        dp = [float('inf')] * size
        dp[0] = 0
        
        for mask in range(size):
            avail = 0
            for i in range(n):
                if not (mask & (1 << i)) and (mask & pre[i]) == pre[i]:
                    avail |= 1 << i
            
            subset = avail
            sub = subset
            while sub:
                if bin(sub).count('1') <= k:
                    dp[mask | sub] = min(dp[mask | sub], dp[mask] + 1)
                sub = (sub - 1) & avail
        
        return dp[size - 1]

Explanation: We first encode prerequisites in a bitmask array. The DP array stores the minimum semesters for each completed-course state. For each state, we calculate available courses, enumerate all valid subsets of size ≤ k, and update the next state in the DP array. Finally, dp[(1 << n) - 1] gives the minimum semesters for completing all courses.

Go Solution

func minNumberOfSemesters(n int, relations [][]int, k int) int {
	pre := make([]int, n)
	for _, r := range relations {
		u, v := r[0]-1, r[1]-1
		pre[v] |= 1 << u
	}
	size := 1 << n
	dp := make([]int, size)
	for i := range dp {
		dp[i] = 1 << 30
	}
	dp[0] = 0

	for mask := 0; mask < size; mask++ {
		avail := 0
		for i := 0; i < n; i++ {
			if mask&(1<<i) == 0 && mask&pre[i] == pre[i] {
				avail |= 1 << i
			}
		}
		sub := avail
		for sub > 0 {
			if bits.OnesCount(uint(sub)) <= k {
				next := mask | sub
				if dp[mask]+1 < dp[next] {
					dp[next] = dp[mask] + 1
				}
			}
			sub = (sub - 1) & avail
		}
	}

	return dp[size-1]
}

Go-specific notes: We use bits.OnesCount to count set bits in a subset, and initialize dp with a large number instead of inf. Subsets are enumerated in the same way as Python using (sub - 1) & avail.

Worked Examples

Example 1: n=4, relations=[[2,1],[3,1],[1,4]], k=2

mask (binary) Courses completed Available courses Action
0000 {} 0100 (2), 0010 (3) Take 2 and 3 → mask=0110
0110 {2,3} 0001 (1) Take 1 → mask=0111
0111 {1,2,3} 1000 (4) Take 4 → mask=1111

Answer: 3 semesters.

Example 2: n=5, relations=[[2,1],[3,1],[4,1],[1,5]], k=2

We iteratively take subsets respecting prerequisites and k=2. After evaluating all states, dp[11111] = 4.

Complexity Analysis

Measure Complexity Explanation
Time O(3^n) Each state enumerates subsets of available courses; there are 2^n states and up to 2^n subsets for each state, but pruning with size ≤ k reduces it to roughly 3^n
Space O(2^n) DP array stores minimum semesters for each bitmask of completed courses

The bitmask DP is efficient for n ≤ 15. Subset enumeration is optimized by only considering subsets of available courses.

Test Cases

# Provided examples
assert Solution().minNumberOfSemesters(4, [[2,1],[3,1],[1,4]], 2) == 3  # Example 1
assert Solution().minNumberOfSemesters(5, [[2,1],[3,1],[4,1],[1,5]], 2) == 4  # Example 2

# No prerequisites, all can be taken at once
assert Solution().minNumberOfSemesters(3, [], 3) == 1

# k = 1, must take one course per semester
assert Solution().minNumberOfSemesters(3, [], 1) == 3

# Complex DAG