#1494

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Parallel Courses II

Determine the minimum semesters to complete all courses with prerequisites using state transition dynamic programming and bitmask tracking.

dynamic programming bit manipulation graph bitmask

Problem Statement

You are given an integer n representing n courses labeled from 1 to n. An array relations is provided where relations[i] = [prevCoursei, nextCoursei] indicates that prevCoursei must be completed before nextCoursei. Additionally, an integer k specifies the maximum number of courses that can be taken in a single semester.

In each semester, you can enroll in at most k courses as long as all their prerequisites have been completed in prior semesters. Return the minimum number of semesters required to complete all courses. It is guaranteed that all courses can eventually be completed.

Examples

Example 1

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

Output: 3

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

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.

Constraints

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.

Solution Approach

Model Prerequisites and States

Represent the set of courses taken as a bitmask and track prerequisites for each course. Each state encodes which courses are completed, allowing the algorithm to efficiently determine which courses are available in the current semester.

Dynamic Programming with Bitmask

Use DP where dp[state] is the minimum number of semesters needed to reach that state. Iterate over all possible subsets of available courses (up to k courses per semester) and update dp[nextState] accordingly. This ensures all valid course combinations are explored while avoiding repeated calculations.

Backtracking and Subset Enumeration

For each state, enumerate all subsets of available courses that fit within the k-course limit. Apply transitions to update the DP table and prune infeasible paths. This approach guarantees the optimal semester count is found while efficiently managing the exponential state space.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * 2^n * C(n, k)) due to iterating over all states and subsets of available courses, while space complexity is O(2^n) to store DP values for each state.

What Interviewers Usually Probe

The problem expects a state transition dynamic programming solution using bitmask representation of course completion.
Consider carefully which courses can be taken each semester based on prerequisites and k-course limits.
Enumerating subsets efficiently and avoiding redundant DP updates demonstrates a strong grasp of the problem pattern.

Common Pitfalls or Variants

Common pitfalls

Failing to track prerequisites accurately can lead to invalid semester counts.
Not limiting course selection to k per semester can produce incorrect solutions.
Redundant state updates without pruning subsets increase runtime and memory usage unnecessarily.

Follow-up variants

Change k dynamically each semester, requiring adaptive DP subset handling.
Introduce weighted courses where semesters count differently based on course load.
Allow optional courses with alternative prerequisites, increasing state complexity.

FAQ

What is the core pattern used in Parallel Courses II?

The problem relies on state transition dynamic programming with bitmask representation to efficiently track completed courses and enforce prerequisites.

How do I determine which courses are available each semester?

Check the prerequisites of each course against the current bitmask state. Only courses with all prerequisites completed can be taken in the current semester.

Why is backtracking needed along with DP?

Backtracking through subsets of available courses allows exploring all valid combinations within the k-course limit while DP stores minimal semester counts for each state.

Can this approach handle n up to 15 efficiently?

Yes, using bitmask DP with subset enumeration keeps the solution feasible because 2^15 states are manageable for modern computation.

What happens if more than k courses are available?

The algorithm enumerates all subsets of size up to k to ensure the per-semester course limit is respected while still progressing optimally.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:
        d = [0] * (n + 1)
        for x, y in relations:
            d[y] |= 1 << x
        q = deque([(0, 0)])
        vis = {0}
        while q:
            cur, t = q.popleft()
            if cur == (1 << (n + 1)) - 2:
                return t
            nxt = 0
            for i in range(1, n + 1):
                if (cur & d[i]) == d[i]:
                    nxt |= 1 << i
            nxt ^= cur
            if nxt.bit_count() <= k:
                if (nxt | cur) not in vis:
                    vis.add(nxt | cur)
                    q.append((nxt | cur, t + 1))
            else:
                x = nxt
                while nxt:
                    if nxt.bit_count() == k and (nxt | cur) not in vis:
                        vis.add(nxt | cur)
                        q.append((nxt | cur, t + 1))
                    nxt = (nxt - 1) & x

Continue Practicing

#847 shortest path visiting all nodes #1434 number of ways to wear different hats to each other #1595 minimum cost to connect two groups of points