Parallel Courses Ii - Leetcode Solution

Problem:

Given the total number of courses and a list of prerequisite pairs, return the minimum number of semesters needed to take all courses. The course requirements are expressed as a pair of courses where the first course is a prerequisite for the second course. It is guaranteed that all prerequisites are unique.

You may assume that there are no duplicate edges in the input prerequisites.

Example 1:

Input: n = 3, dependencies = [[1,3],[2,3]] Output: 2 Explanation: In the first semester, courses 1 and 2 are taken. In the second semester, course 3 is taken.

Example 2:

Input: n = 3, dependencies = [[1,2],[2,3],[3,1]] Output: -1 Explanation: No course can be taken because they depend on each other.

Solution:

This problem can be solved by topological sorting. We will use a variation of Kahn's algorithm to find the topological order of the graph. In order to calculate the minimum number of semesters, we will group the courses into semesters. Each semester can contain multiple courses.

Step 1: Create a graph using the given dependencies

We will create a directed graph using the given dependencies. Each course will be a node in the graph and its prerequisites will be its incoming edges.

Step 2: Calculate the in-degree of each node

We will calculate the in-degree of each node (i.e., the number of incoming edges). We will use an array of size n to store this information.

Step 3: Create a queue and add all nodes with zero in-degree

We will create a queue and add all nodes with zero in-degree to it. These are the nodes that can be taken in the first semester.

Step 4: Process the queue and update the in-degree of neighboring nodes

We will process the queue and update the in-degree of all neighboring nodes. If a neighboring node has zero in-degree after removing the edge, we will add it to the queue. We will repeat this process until the queue is empty.

Step 5: Increment the semester counter and repeat Step 4

After processing the queue, we will increment the semester counter and repeat Step 4. The nodes in the queue will represent the courses that can be taken in the current semester.

Step 6: Check if all courses have been taken

If all courses have been taken, we will return the semester counter. Otherwise, we will return -1 to indicate that all courses cannot be taken.

Implementation:

Here is the Python implementation of the above algorithm:

def parallelCourses(n: int, dependencies: List[List[int]]) -> int: # Step 1: Create a graph using the given dependencies graph = [[] for _ in range(n)] for u, v in dependencies: graph[u - 1].append(v - 1)

# Step 2: Calculate the in-degree of each node
in_degree = [0] * n
for u in range(n):
    for v in graph[u]:
        in_degree[v] += 1

# Step 3: Create a queue and add all nodes with zero in-degree
queue = []
for u in range(n):
    if in_degree[u] == 0:
        queue.append(u)

# Initialize the semester counter
semesters = 0

# Step 4: Process the queue and update the in-degree of neighboring nodes
while queue:
    # Increment the semester counter
    semesters += 1

    # Take all the courses in the current semester
    for _ in range(len(queue)):
        u = queue.pop(0)

        # Step 5: Update the in-degree of neighboring nodes
        for v in graph[u]:
            in_degree[v] -= 1

            # Add the node to the queue if its in-degree becomes zero
            if in_degree[v] == 0:
                queue.append(v)

# Step 6: Check if all courses have been taken
if sum(in_degree) == 0:
    return semesters
else:
    return -1

Time Complexity: O(n + m), where n is the number of courses and m is the number of dependencies. We traverse each node and edge only once.

Space Complexity: O(n + m), where n is the number of courses and m is the number of dependencies. We use an array of size n to store the in-degree information and a queue of size m at most to store the nodes. We also use a graph of size m to represent the dependencies.

1