Problem Description

The Parallel Courses problem asks you to determine the minimum number of semesters required to complete n courses given a list of prerequisite relationships. Each prerequisite is a pair [prevCourse, nextCourse], meaning you must complete prevCourse before taking nextCourse. In each semester, you can take any number of courses as long as all their prerequisites have been completed in previous semesters. The task is to return the minimum number of semesters needed to finish all courses, or -1 if it's impossible due to cyclic dependencies.

• Each course is labeled from 1 to n.
• All prerequisites must be satisfied before taking a course.
• You may take multiple courses in parallel in a semester, as long as their prerequisites are satisfied.
• Return -1 if it's not possible to finish all courses (i.e., there is a cycle).

Thought Process

At first glance, the problem resembles the classic "Course Schedule" or "Topological Sort" challenge. The key difference is that we want to minimize the number of semesters, taking as many eligible courses as possible in each semester. A brute-force approach might try all possible combinations of course selections per semester, but this quickly becomes intractable as the number of courses increases.

Instead, we can think of the problem as finding the "longest path" in a directed acyclic graph (DAG) formed by the prerequisite relationships. Each semester corresponds to moving one level deeper in the dependency graph: in semester 1, we take all courses with no prerequisites; in semester 2, we take all courses whose prerequisites were completed in semester 1, and so on. If the graph contains a cycle, it's impossible to complete all courses.

Therefore, the solution requires:

• Detecting cycles in the dependency graph.
• Calculating the minimum number of semesters as the number of "layers" or levels in the graph.

Solution Approach

We solve this problem using a modified topological sort (BFS) approach:

1. Build the Graph:
   • Use an adjacency list to represent the graph: for each course, store the list of courses that depend on it.
   • Keep an in-degree array to count how many prerequisites each course has.
2. Initialize the Queue:
   • Add all courses with zero in-degree (no prerequisites) to a queue. These can be taken in the first semester.
3. Process by Semesters:
   • For each semester, process all courses currently in the queue (these are eligible to be taken now).
   • For each course taken, reduce the in-degree of its dependent courses by one.
   • If any dependent course's in-degree drops to zero, add it to the queue for the next semester.
   • Increment the semester count after processing each batch.
4. Cycle Detection:
   • Keep a count of how many courses have been processed. If this count is less than n at the end, a cycle exists, so return -1.
5. Return the Result:
   • The number of semesters processed is the answer.

This approach is efficient because each course and prerequisite is processed only once, and the BFS ensures we take as many courses as possible each semester.

Example Walkthrough

Example Input:
n = 4, prerequisites = [[2,1],[3,1],[1,4]]

Step-by-step:

• Build the graph:
  • 2 → 1
  • 3 → 1
  • 1 → 4
• In-degree array: [0, 2, 0, 1] (courses 2 and 3 have 0 prerequisites, 1 has 2, 4 has 1)
• Semester 1: Take courses 2 and 3 (in-degree 0). After taking them, course 1's in-degree becomes 0.
• Semester 2: Take course 1 (now in-degree 0). After taking it, course 4's in-degree becomes 0.
• Semester 3: Take course 4.
• All courses are taken in 3 semesters.

Result: 3

Time and Space Complexity

Brute-force Approach:

• Would involve checking all possible orderings of courses, which is factorial time: O(n!). This is not feasible for large n.

• Time Complexity: O(n + m), where n is the number of courses and m is the number of prerequisite pairs. Each course and edge is processed once.
• Space Complexity: O(n + m) for the adjacency list and in-degree array.

This makes the optimized approach suitable for large inputs.

Summary

The Parallel Courses problem is a classic application of topological sorting in a directed acyclic graph. By leveraging BFS and processing the graph layer by layer, we efficiently determine the minimum number of semesters required to complete all courses, while also detecting cycles that make completion impossible. The key insight is to take as many eligible courses in parallel as possible each semester, corresponding to the longest path in the dependency graph.

Code Implementation

from collections import deque, defaultdict

class Solution:
    def minimumSemesters(self, n, relations):
        graph = defaultdict(list)
        indegree = [0] * (n + 1)

        for prev, nextc in relations:
            graph[prev].append(nextc)
            indegree[nextc] += 1

        queue = deque()
        for course in range(1, n + 1):
            if indegree[course] == 0:
                queue.append(course)

        semesters = 0
        taken = 0

        while queue:
            for _ in range(len(queue)):
                course = queue.popleft()
                taken += 1
                for neighbor in graph[course]:
                    indegree[neighbor] -= 1
                    if indegree[neighbor] == 0:
                        queue.append(neighbor)
            semesters += 1

        return semesters if taken == n else -1
      

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int minimumSemesters(int n, vector<vector<int>>& relations) {
        vector<vector<int>> graph(n + 1);
        vector<int> indegree(n + 1, 0);

        for (auto &rel : relations) {
            graph[rel[0]].push_back(rel[1]);
            indegree[rel[1]]++;
        }

        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            if (indegree[i] == 0) q.push(i);
        }

        int semesters = 0, taken = 0;
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; ++i) {
                int course = q.front(); q.pop();
                taken++;
                for (int neighbor : graph[course]) {
                    indegree[neighbor]--;
                    if (indegree[neighbor] == 0) q.push(neighbor);
                }
            }
            semesters++;
        }

        return taken == n ? semesters : -1;
    }
};
      

import java.util.*;

class Solution {
    public int minimumSemesters(int n, int[][] relations) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        int[] indegree = new int[n + 1];

        for (int[] rel : relations) {
            graph.get(rel[0]).add(rel[1]);
            indegree[rel[1]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }

        int semesters = 0, taken = 0;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
                int course = queue.poll();
                taken++;
                for (int neighbor : graph.get(course)) {
                    indegree[neighbor]--;
                    if (indegree[neighbor] == 0) queue.offer(neighbor);
                }
            }
            semesters++;
        }
        return taken == n ? semesters : -1;
    }
}
      

/**
 * @param {number} n
 * @param {number[][]} relations
 * @return {number}
 */
var minimumSemesters = function(n, relations) {
    const graph = Array.from({length: n + 1}, () => []);
    const indegree = Array(n + 1).fill(0);

    for (const [prev, next] of relations) {
        graph[prev].push(next);
        indegree[next]++;
    }

    const queue = [];
    for (let i = 1; i <= n; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    let semesters = 0, taken = 0;
    while (queue.length > 0) {
        const sz = queue.length;
        for (let i = 0; i < sz; i++) {
            const course = queue.shift();
            taken++;
            for (const neighbor of graph[course]) {
                indegree[neighbor]--;
                if (indegree[neighbor] === 0) queue.push(neighbor);
            }
        }
        semesters++;
    }
    return taken === n ? semesters : -1;
};