Parallel Courses II

Hard

Asked by:

14 views

Topics:

GraphsDynamic ProgrammingBit Manipulation

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given an array relations where relations[i] = [prevCourse_i, nextCourse_i], representing a prerequisite relationship between course prevCourse_i and course nextCourse_i: course prevCourse_i has to be taken before course nextCourse_i. Also, you are given the integer k.

In one semester, you can take at most k courses as long as you have taken all the prerequisites in the previous semesters for the courses you are taking.

Return the minimum number of semesters needed to take all courses. The testcases will be generated such that it is possible to take every course.

Example 1:

Input: n = 4, relations = [[2,1],[3,1],[1,4]], k = 2
Output: 3
Explanation: 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
Explanation: 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 <= prevCourse_i, nextCourse_i <= n
prevCourse_i != nextCourse_i
All the pairs [prevCourse_i, nextCourse_i] are unique.
The given graph is a directed acyclic graph.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the number of courses (n) and the number of prerequisites (relations)? Are there upper bounds that I should be aware of?
Can a course have multiple prerequisites, and can a prerequisite be required for multiple courses?
Is it guaranteed that it's always possible to complete all the courses, or should I return a specific value (e.g., -1) if a cycle exists and it's impossible?
What are the constraints on k, the maximum number of courses that can be taken in parallel? Can k be zero or larger than the number of courses remaining?
Are the course numbers zero-indexed or one-indexed?

Brute Force Solution

Approach

The brute force approach to this problem is all about trying every single combination of courses we can take in each semester. We'll explore all possible valid selections, making sure we're always meeting the course prerequisites.

Here's how the algorithm would work step-by-step:

Start by considering all possible sets of courses you could take in the very first semester, making sure you don't take more courses than allowed.
For each of these possible sets of courses, check if you've met all the prerequisites for those courses.
If a set of courses is valid (meets prerequisites), move on to the next semester and again, consider all possible sets of courses you could take that semester, considering only courses not already taken.
Again, check the prerequisites for each of those sets of courses.
Keep doing this, semester by semester, until you have taken all the courses.
For each way of completing all courses, record how many semesters it took.
Finally, compare all the different ways you found and pick the one that took the fewest semesters.

Code Implementation

def parallel_courses_two_brute_force(number_of_courses, prerequisites, max_courses):
    all_courses = set(range(1, number_of_courses + 1))
    
    def can_take_courses(available_courses, current_semester_courses, all_prerequisites):
        for course in current_semester_courses:
            for prerequisite_course, dependent_course in all_prerequisites:
                if course == dependent_course and prerequisite_course not in available_courses and prerequisite_course not in current_semester_courses:
                    return False
        return True

    def solve(taken_courses, semester_count):
        if taken_courses == all_courses:
            return semester_count

        remaining_courses = all_courses - taken_courses
        minimum_semesters = float('inf')

        # Try every possible combination of courses this semester
        for i in range(1 << len(remaining_courses)):
            current_semester_courses = set()
            count = 0
            course_index = 0
            remaining_courses_list = list(remaining_courses)

            for course in remaining_courses_list:
                if (i >> course_index) & 1:
                    current_semester_courses.add(course)
                    count += 1
                course_index += 1

            if count > max_courses:
                continue

            # Make sure we can take all courses in this semester
            if can_take_courses(taken_courses, current_semester_courses, prerequisites):
                new_taken_courses = taken_courses | current_semester_courses
                minimum_semesters = min(minimum_semesters, solve(new_taken_courses, semester_count + 1))

        return minimum_semesters

    # Begin the search with no courses taken and 0 semesters used.
    return solve(set(), 0)

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible combinations of courses to take each semester. In the worst-case scenario, we could potentially consider every subset of courses for each semester. Since there are n courses, there are 2^n possible subsets. The algorithm iterates through these subsets to find the optimal combination, leading to an exponential time complexity. Therefore, the Big O time complexity is O(2^n).

Space Complexity

O(2^N) – The brute force approach explores all possible combinations of courses taken each semester. In the worst-case scenario, the algorithm may need to store a large number of intermediate results corresponding to the different combinations of courses taken and the number of semesters used to reach that intermediate state. The number of possible subsets of courses is 2^N where N is the number of courses. The recursion stack would also contribute to the auxiliary space as we explore different combinations of taking each course, leading to a potential stack depth proportional to the number of courses. Therefore, the auxiliary space complexity is O(2^N).

Optimal Solution

Approach

The problem requires taking the minimum number of semesters to complete courses with prerequisites and a maximum course limit per semester. The key is to represent course completion as a state and use dynamic programming to explore possible states while intelligently pruning the search space.

Here's how the algorithm would work step-by-step:

Represent each course as a bit in a number; a '1' means the course is completed and a '0' means it's not.
Calculate the prerequisites for each course; this means figuring out which courses must be completed before you can start a particular course.
Use a technique to store the minimum semesters needed to reach a certain state; the state is all courses that are completed at a certain time.
Start completing courses, one semester at a time.
For each semester, look at which courses you can take, given the courses you have already completed and the prerequisites for each course.
Consider all possible combinations of courses you can take this semester, making sure that you don't exceed the maximum number of courses you can take in one semester.
Choose the best possible combination of courses to take in this semester, which results in the smallest number of semesters needed to reach a certain state.
Repeat this process until all courses are completed. The number of semesters it took to complete all courses is the answer.

Code Implementation

def parallel_courses_two(number_of_courses, prerequisites, max_courses):
    course_dependencies = [[] for _ in range(number_of_courses)]
    incoming_edges = [0] * number_of_courses

    for prerequisite, course in prerequisites:
        course_dependencies[prerequisite - 1].append(course - 1)
        incoming_edges[course - 1] += 1

    # Represent each course completion state as a bitmask
    all_courses_completed = (1 << number_of_courses) - 1
    min_semesters_needed = {0: 0}

    for current_state in range(all_courses_completed + 1):
        if current_state not in min_semesters_needed:
            continue

        available_courses = []
        for course_index in range(number_of_courses):
            if (current_state >> course_index) & 1 == 0:
                ready = True
                for dependency in course_dependencies[course_index]:
                    if (current_state >> dependency) & 1 == 0:
                        ready = False
                        break
                if ready:
                    available_courses.append(course_index)

        # Iterate through all possible combinations of courses
        for combination_mask in range(1 << len(available_courses)):
            if bin(combination_mask).count('1') > max_courses:
                continue

            next_state = current_state
            courses_taken_count = 0
            for course_index_in_available in range(len(available_courses)):
                if (combination_mask >> course_index_in_available) & 1:
                    next_state |= (1 << available_courses[course_index_in_available])
                    courses_taken_count +=1

            # Update the minimum semesters needed for the next state
            if next_state not in min_semesters_needed:
                min_semesters_needed[next_state] = float('inf')

            # Dynamically update the min_semesters_needed dictionary
            min_semesters_needed[next_state] = min(min_semesters_needed[next_state], min_semesters_needed[current_state] + 1)

    return min_semesters_needed[all_courses_completed]

Big(O) Analysis

Time Complexity

O(2^n * n * n) – The algorithm uses dynamic programming to explore all possible states of course completion, where each course can be either completed or not. This leads to 2^n possible states. For each state, we need to iterate through all the courses (n) to find the available courses that can be taken in the current semester. Then, for each combination of possible courses to take (at most n), we update the dp table. Therefore, the overall time complexity is approximately O(2^n * n * n), where the first n is for iterating courses in a given state and the second n results from the combinations of courses. The k parameter, max number of courses in a semester, impacts the constant factor but not the overall Big O.

Space Complexity

O(2^N) – The algorithm utilizes dynamic programming to store the minimum semesters needed to reach each possible state of course completion. Each course can either be completed or not, leading to 2^N possible states, where N is the number of courses. Therefore, a DP table or a hash map of size 2^N is used to store intermediate results for each state. This results in the space complexity being directly proportional to the number of possible states, which is 2^N.

Edge Cases

Case	How to Handle
n = 0 (no courses)	Return 0, as no semesters are needed to complete no courses.
k = 0 (cannot take any courses)	Return -1, as it's impossible to finish any course if no courses can be taken each semester.
No prerequisites (all courses can be taken in parallel)	Return ceiling(n / k), the minimum number of semesters needed to take all courses in parallel.
Cyclic dependencies (impossible to complete courses)	Detect cycles using topological sort or similar, and return -1 if a cycle exists.
n = 1 (single course)	Return 1 if there are no prerequisites, otherwise, check prerequisites and proceed.
Maximum sized inputs (n and k are large)	Optimize dynamic programming states and transitions to avoid exceeding time or memory limits using bitmasking efficiently.
Courses with many prerequisites and dependencies, but k is small	The algorithm correctly prioritizes completing courses that unlock the most future courses given the limit 'k' courses each semester.
Integer overflow when calculating bitmasks for course dependencies.	Use appropriate data types like long or unsigned long to prevent overflow when representing dependencies with bitmasks.

n = 0 (no courses)

How to Handle:

Return 0, as no semesters are needed to complete no courses.

k = 0 (cannot take any courses)

How to Handle:

Return -1, as it's impossible to finish any course if no courses can be taken each semester.

No prerequisites (all courses can be taken in parallel)

How to Handle:

Return ceiling(n / k), the minimum number of semesters needed to take all courses in parallel.

Cyclic dependencies (impossible to complete courses)

How to Handle:

Detect cycles using topological sort or similar, and return -1 if a cycle exists.

n = 1 (single course)

How to Handle:

Return 1 if there are no prerequisites, otherwise, check prerequisites and proceed.

Maximum sized inputs (n and k are large)

How to Handle:

Optimize dynamic programming states and transitions to avoid exceeding time or memory limits using bitmasking efficiently.

Courses with many prerequisites and dependencies, but k is small

How to Handle:

The algorithm correctly prioritizes completing courses that unlock the most future courses given the limit 'k' courses each semester.

Integer overflow when calculating bitmasks for course dependencies.

How to Handle:

Use appropriate data types like long or unsigned long to prevent overflow when representing dependencies with bitmasks.