1494. Parallel Courses II

HardBit ManipulationGraphDynamic ProgrammingBitmask
Leetcode Link

Problem Description

In this problem, you're essentially a student planning out your semesters in advance to ensure you can take all the courses you need to graduate. You've got n different courses numbered from 1 to n, and a list of prerequisite relationships such that you have to complete some courses before starting others. These prerequisites are indicated by pairs [prevCourse, nextCourse] where prevCourse is a course you must take before nextCourse.

You have one more constraint: in any given semester, you can only take up to k courses. Given these rules, your challenge is to determine the minimum number of semesters required to complete all n courses. The problem guarantees that it's possible to take all courses by eventually meeting all prerequisites.

Intuition

The core of the solution lies in understanding that this is a scheduling problem that can be represented as a directed graph, where each node is a course, and the edges represent prerequisite relationships. To minimize the number of semesters, we want to take as many courses as we can each semester, taking care not to exceed the limit k and ensuring we've completed all prerequisites needed.

To approach this algorithmically, we represent our course schedule using bit manipulation, where a bit set to 1 indicates a course is completed. We initialize with 0, representing that no courses have been taken. Each bit position corresponds to a specific course, so an integer can represent any combination of completed courses.

We iterate over all courses, checking prerequisites using bitwise AND operations. If a course's prerequisites are satisfied, indicated by a 1 in all prerequisite course's positions in our bitmask, we can consider it for selection in the current semester.

The challenge involves choosing the right courses when facing the k course limit. We use depth-first search to traverse the different combinations of courses we can take each semester, branching out into different scenarios and making sure we don't revisit the same state (combination of courses) again.

The algorithm uses a queue to process these combinations in a breadth-first manner. For each state, we branch into new states that represent taking a different subset of k or fewer courses, marking states as visited to avoid redundant work. We repeat this until we reach a state where all courses are complete, and since we're using breadth-first search, the first time we reach this state will be the minimum number of semesters required.

The bit_count method (in Python, you might see this as bin(x).count('1') or a similar alternative) is used to quickly count the number of bits set to 1 to ensure we don't exceed k courses in a semester. When we have a selection of courses that meets the prerequisites and doesn't exceed the k limit, we add that state to our queue and continue the search until we've found the optimal number of semesters.

Learn more about Graph, Dynamic Programming and Bitmask patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

In a binary min heap, the maximum element can be found in:

Solution Approach

The solution employs bit manipulation, breadth-first search, and a queue data structure to efficiently explore different possibilities for course schedules while tracking progress and prerequisites.

Here's a step-by-step breakdown of the implementation:

  • Each combination of completed courses is represented as a bit sequence, with 1s indicating completed courses. A deque (double-ended queue) from Python's collections is initiated with the starting point (0, 0), which represents no courses taken (0) in 0 semesters.

  • A vis (visited) set is used to record states we have already considered, preventing us from repeating the same combinations, and thus reducing unnecessary computations.

  • The core of the solution is a loop that continues as long as there are states in our queue to process. On each iteration, we:

    • Pop the first state cur from the deque, which represents the current combination of courses taken up to the present, and t, the number of semesters taken so far.

    • If cur matches our goal state (1 << (n + 1)) - 2, which means all courses except the course numbered 0 (which doesn't exist) are completed, we return t as the minimum number of semesters needed.

    • Calculate which new courses (nxt) can be taken given the current state. This involve iterating over each course i and checking if its prerequisites (d[i]) are all in cur. If yes, this course can be added (nxt |= 1 << i).

    • Remove courses from nxt that are already in cur, leaving a bitmask of courses that are potential candidates for the current semester.

    • If the number of potential courses is less than or equal to k, we can take all of them in the current semester. The new state (nxt | cur) is added to the queue if it's not already visited.

    • If there are more than k courses available, we have to consider all subsets of nxt of size k and put each into the queue if not visited. This is done through a combination of bit manipulation steps that count the bits, check the subset size, and ensure all subsets are considered.

Overall, the solution uses a breadth-first search to traverse through a graph representation of course schedules. The graph is implicit, with each node (state) representing a set of completed courses, and edges determined by possible courses to be taken each semester, following prerequisites and the limit k. Bit manipulation allows efficient representation and manipulation of course combinations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Assume we have n = 4 different courses with corresponding prerequisite pairs [[1, 2], [1, 3], [3, 4]], indicating that you must complete course 1 before taking courses 2 and 3, and course 3 before taking course 4. We also have a limit k = 2, meaning you can take up to two courses in any given semester.

Let's walk through an application of the solution approach:

  1. Initialization: We represent our course schedule with bit manipulation:

    • No courses are taken initially, so our starting bit sequence is 0000.
    • We begin with a deque initialized with this starting state (0, 0), meaning no courses have been completed and 0 semesters have passed.
    • We also initialize a vis (visited) set to keep track of states we've already examined.

  2. Process Queue:

    • We start processing the states in our queue.
    • Our goal state is (1 << (n + 1)) - 2 = 1110, representing all courses except the non-existent course 0 being completed. (The bit sequence uses n+1 because we are using 1-indexing for our courses.)

  3. Selecting Courses:

    • At the start, with the current state being 0000, we identify which courses have their prerequisites fulfilled and can be taken. Course 1 has no prerequisites, so it can be taken immediately, resulting in the next state being 0001.
    • We then add (0001, 1) to our queue to represent that course 1 is completed after 1 semester.

  4. Branching for the Next Semester:

    • We dequeue the state (0001, 1) and identify potential new courses that can be taken. Given the prerequisites, we can now take courses 2 and 3, resulting in the bitmask 0110.
    • We now have three potential states to consider for the next semester: 0101, 0011, and 0110. Each of these represents taking either course 2 or 3 along with the already completed course 1, fulfilling the prerequisite conditions.

  5. Considering Course Limit k:

    • The limit of k=2 means we can only consider combinations of up to 2 courses per semester. Since we do not exceed this limit by taking either course 2 or 3, we can add both states 0101 and 0011 to our queue.

  6. Reaching the Goal:

    • Proceeding with either of the new states (0101 or 0011), we follow similar steps and eventually can take course 4, leading us to our goal state of 1110 after a minimum of 2 semesters, since by the second semester all prerequisites for the remaining courses would have been satisfied, allowing us to take the final course and complete the schedule.

In conclusion, using this example with n = 4, prerequisites [[1, 2], [1, 3], [3, 4]], and course limit k = 2, we can see that the minimum number of semesters required to complete all courses is 2. This approach, combining bit manipulation, a queue, and breadth-first search, allows us to efficiently arrive at this solution.

Solution Implementation

1from collections import deque
2from typing import List
3
4class Solution:
5    def minNumberOfSemesters(self, num_courses: int, prerequisites: List[List[int]], max_courses_per_semester: int) -> int:
6        # Initialize the bitwise representation for the prerequisites of each course
7        prereq_masks = [0] * (num_courses + 1)
8      
9        # Populate the prerequisite mask for each course
10        for x, y in prerequisites:
11            prereq_masks[y] |= 1 << x
12      
13        # Initialize the queue with the starting point (0 courses taken, 0 semesters passed)
14        queue = deque([(0, 0)])
15        visited = {0}  # Set to hold visited states to avoid revisiting
16      
17        while queue:
18            courses_taken, semesters = queue.popleft()
19          
20            # If all courses have been taken, return the number of semesters it took
21            if courses_taken == (1 << (num_courses + 1)) - 2:
22                return semesters
23          
24            # Find the courses that are now free to be taken
25            eligible_courses = 0
26            for i in range(1, num_courses + 1):
27                if (courses_taken & prereq_masks[i]) == prereq_masks[i]:
28                    eligible_courses |= 1 << i
29            eligible_courses ^= courses_taken
30          
31            # If the number of eligible courses is less than or equal to the max per semester, take them all
32            if bin(eligible_courses).count('1') <= max_courses_per_semester:
33                next_state = eligible_courses | courses_taken
34                if next_state not in visited:
35                    visited.add(next_state)
36                    queue.append((next_state, semesters + 1))
37            else:
38                # If we have more courses available than we can take, choose max allowed number of courses
39                course_combinations = eligible_courses
40                while eligible_courses:
41                    # If the combination is valid, consider it as a possibility and add to the queue
42                    if bin(eligible_courses).count('1') == max_courses_per_semester and ((eligible_courses | courses_taken) not in visited):
43                        visited.add(eligible_courses | courses_taken)
44                        queue.append((eligible_courses | courses_taken, semesters + 1))
45                    # Use bitmask to find the next combination of courses
46                    eligible_courses = (eligible_courses - 1) & course_combinations
47
48# Example usage:
49# sol = Solution()
50# res = sol.minNumberOfSemesters(4, [[2,1],[3,1],[1,4]], 2)
51# print(res) # Output should be the minimum number of semesters to take all courses
52
1import java.util.ArrayDeque;
2import java.util.Deque;
3import java.util.HashSet;
4import java.util.Set;
5
6class Solution {
7    public int minNumberOfSemesters(int n, int[][] relations, int k) {
8        // Initialization of dependencies for each course
9        int[] dependencies = new int[n + 1];
10        for (int[] relation : relations) {
11            // Represent the dependencies in a bit mask, where each bit represents a course
12            dependencies[relation[1]] |= 1 << relation[0];
13        }
14      
15        // Queue for BFS, holding pairs of integers representing current state and time (semesters)
16        Deque<int[]> queue = new ArrayDeque<>();
17        queue.offer(new int[] {0, 0}); // Start with {state, semesters} = {0, 0}
18      
19        // Visited states hash set to avoid revisiting the same state
20        Set<Integer> visited = new HashSet<>();
21        visited.add(0);
22      
23        while (!queue.isEmpty()) {
24            int[] pair = queue.pollFirst();
25            int currentState = pair[0];
26            int semesters = pair[1];
27          
28            // If all courses have been taken, return the number of semesters
29            if (currentState == (1 << n) - 1) {
30                return semesters;
31            }
32          
33            // Find the next set of courses we can take based on current state
34            int next = 0;
35            for (int i = 1; i <= n; ++i) {
36                if ((currentState & dependencies[i]) == dependencies[i]) {
37                    // Course i's dependencies are satisfied, mark as potential next course
38                    next |= 1 << i;
39                }
40            }
41            // Remove courses we've already taken from the potential next courses
42            next &= ~currentState;
43          
44            // If the number of available courses is less than or equal to k, take them all
45            if (Integer.bitCount(next) <= k) {
46                if (visited.add(next | currentState)) {
47                    queue.offer(new int[] {next | currentState, semesters + 1});
48                }
49            } else {
50                // Otherwise, we will need to pick k courses from the available ones
51                int combinations = next;
52                do {
53                    if (Integer.bitCount(combinations) == k && visited.add(combinations | currentState)) {
54                        queue.offer(new int[] {combinations | currentState, semesters + 1});
55                    }
56                    // Generate the next combination of courses
57                    combinations = (combinations - 1) & next;
58                } while (combinations != 0);
59            }
60        }
61      
62        // If no solution is found, return 0 (though the problem statement should guarantee a solution)
63        return 0;
64    }
65}
66
1class Solution {
2public:
3    // Method to calculate the minimum number of semesters to take all courses
4    int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
5        // Initialize a vector to keep track of course prerequisites using bitmasking
6        vector<int> prerequisites(n + 1, 0);
7        // Process the relations to set up the prerequisites mask for each course
8        for (const auto& relation : relations) {
9            prerequisites[relation[1]] |= 1 << relation[0];
10        }
11      
12        // Queue to hold pairs of courses taken and number of semesters
13        queue<pair<int, int>> coursesQueue;
14        // Starting condition
15        coursesQueue.push({0, 0});
16        // Set to keep track of visited states
17        unordered_set<int> visited{{0}};
18      
19        // Continue until the queue is empty
20        while (!coursesQueue.empty()) {
21            auto [currentCourses, semesters] = coursesQueue.front(); // Get the front pair
22            coursesQueue.pop();
23          
24            // If all courses have been taken (all bits set except the 0th bit), return the semesters
25            if (currentCourses == (1 << (n + 1)) - 2) {
26                return semesters;
27            }
28          
29            // Compute the next set of courses that can be taken
30            int nextCourses = 0;
31            for (int i = 1; i <= n; ++i) {
32                if ((currentCourses & prerequisites[i]) == prerequisites[i]) {
33                    nextCourses |= 1 << i;
34                }
35            }
36            // XOR with current courses to get courses not yet taken
37            nextCourses ^= currentCourses;
38          
39            // If the number of next courses is less than or equal to k, proceed
40            if (__builtin_popcount(nextCourses) <= k) {
41                int combinedCourses = nextCourses | currentCourses;
42                if (!visited.count(combinedCourses)) {
43                    visited.insert(combinedCourses);
44                    coursesQueue.push({combinedCourses, semesters + 1});
45                }
46            } else {
47                // If more than k courses are available to take, iterate through combinations
48                int x = nextCourses;
49                while (nextCourses) {
50                    // If exactly k unvisited courses can be taken
51                    if (__builtin_popcount(nextCourses) == k && !visited.count(nextCourses | currentCourses)) {
52                        visited.insert(nextCourses | currentCourses);
53                        coursesQueue.push({nextCourses | currentCourses, semesters + 1});
54                    }
55                    // Generate the next smaller combination of courses to take
56                    nextCourses = (nextCourses - 1) & x;
57                }
58            }
59        }
60        // If all courses have not been taken, return 0
61        return 0;
62    }
63};
64
1// Function to calculate the minimum number of semesters to take all courses
2function minNumberOfSemesters(n: number, relations: number[][], k: number): number {
3    // Initialize an array to keep track of course prerequisites using bitmasking
4    let prerequisites = new Array(n + 1).fill(0);
5    // Process the relations to set up the prerequisites mask for each course
6    relations.forEach(relation => {
7        prerequisites[relation[1]] |= 1 << (relation[0] - 1);
8    });
9
10    // Queue to hold pairs of courses taken and number of semesters
11    let coursesQueue: Array<{ currentCourses: number; semesters: number }> = [];
12    // Starting condition
13    coursesQueue.push({ currentCourses: 0, semesters: 0 });
14
15    // Set to keep track of visited states
16    let visited: Set<number> = new Set();
17    visited.add(0);
18
19    // Continue until the queue is empty
20    while (coursesQueue.length > 0) {
21        let { currentCourses, semesters } = coursesQueue.shift()!;
22
23        // If all courses have been taken (all bits set but 0th bit), return the semesters
24        if (currentCourses === (1 << n) - 1) {
25            return semesters;
26        }
27
28        // Compute the next set of courses that can be taken
29        let nextCourses = 0;
30        for (let i = 0; i < n; ++i) {
31            if ((currentCourses & prerequisites[i + 1]) === prerequisites[i + 1]) {
32                nextCourses |= 1 << i;
33            }
34        }
35        // XOR with current courses to get courses not yet taken
36        nextCourses ^= currentCourses;
37
38        // If the number of next courses is less than or equal to k, proceed
39        if (countSetBits(nextCourses) <= k) {
40            let combinedCourses = nextCourses | currentCourses;
41            if (!visited.has(combinedCourses)) {
42                visited.add(combinedCourses);
43                coursesQueue.push({ currentCourses: combinedCourses, semesters: semesters + 1 });
44            }
45        } else {
46            // If more than k courses are available to take, iterate through combinations
47            let x = nextCourses;
48            while (nextCourses) {
49                // If exactly k unvisited courses can be taken
50                if (countSetBits(nextCourses) === k && !visited.has(nextCourses | currentCourses)) {
51                    visited.add(nextCourses | currentCourses);
52                    coursesQueue.push({ currentCourses: nextCourses | currentCourses, semesters: semesters + 1 });
53                }
54                // Generate the next smaller combination of courses to take
55                nextCourses = (nextCourses - 1) & x;
56            }
57        }
58    }
59    // If all courses have not been taken, return 0
60    return 0;
61}
62
63// Helper function to count the number of set bits in a number (equivalent to __builtin_popcount in C++)
64function countSetBits(n: number): number {
65    let count = 0;
66    while (n) {
67        count += n & 1;
68        n >>>= 1;
69    }
70    return count;
71}
72
Not Sure What to Study? Take the 2-min Quiz

What data structure does Breadth-first search typically uses to store intermediate states?

Time and Space Complexity

The given Python code aims to find the minimum number of semesters to take all courses given pre-requisite relations and a limit on the number of courses that can be taken in one semester. The code employs a breadth-first search (BFS) strategy.

Time Complexity

Let n be the number of courses and k be the maximum number of courses that can be taken in a semester. The time complexity primarily depends on the operations inside the while-loop.

  • The BFS explores all possible combinations of courses one can take each semester.
  • For each state in the queue, the code first identifies all courses whose prerequisites are satisfied (the for-loop over n courses), which takes O(n) time.
  • The main complexity comes from generating the next set of courses to take. In the worst case, it iterates through all combinations of courses that can be taken in the next step. Since there are n courses, there can be up to 2^n combinations. However, because we only care about combinations of size k, the number of combinations checked effectively becomes C(n,k) (combinatorial), which is upper-bounded by O(n^k).
  • Each level of BFS, therefore, has a maximum time complexity of O(n * n^k) since we multiply the number of operations to identify the next set of courses O(n^k) by the operations required to find the courses that can be taken O(n).

Hence, the time complexity is O((2^n) * (n * n^k)). Since C(n, k) is smaller than 2^n for small values of k, a tighter bound could be O((2^n) * n * C(n, k)).

Space Complexity

  • The space complexity involves storing the queue and the visited states.
  • Each state is a bitmask of length n, and there are 2^n possible states. However, due to the pruning by checking visited states, not all states will be stored in the vis set simultaneously.
  • The space complexity becomes O(2^n) for storing visited states, which is the dominant factor compared to the queue.

Overall, the space complexity is O(2^n). Note that this analysis assumes that standard operations like bit-counting take O(1) time, which is typically the case in modern architectures.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Recommended Readings

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Bitmask Introduction

Bitmask and Dynamic Programming Bit manipulation is a crucial aspect of computer programming and one of the most powerful tools for bit manipulation is bitmasks Let's first understand what a bit is A bit is a binary digit It's the smallest piece of data in a computer and can be

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«