LeetCode Solutions Blog

Parallel Courses III

Number: 2176

Difficulty: Hard

Paid? No

Problem Description

Given n courses (labeled 1 to n) with prerequisite relations and the time each course takes, determine the minimum number of months required to complete all courses. Multiple courses may be taken simultaneously as long as prerequisites are met. The prerequisites form a Directed Acyclic Graph (DAG).

Key Insights

The prerequisite relationships form a DAG.
The minimum time to finish all courses is determined by the longest path (in terms of total course time) in the DAG.
Use topological sort to process courses in an order that respects prerequisites.
Utilize dynamic programming: for each course, record the earliest finishing time considering the maximum finishing time among its prerequisites.

Space and Time Complexity

Time Complexity: O(n + m) where m is the number of prerequisite relations. Space Complexity: O(n + m) for storing the graph and auxiliary data structures.

Solution

The solution involves:

Building an adjacency list for the graph and computing the in-degree for each course.
Using a queue to perform a topological sort. Courses with 0 in-degree can be started immediately.
Initializing a dp array (or similar) where dp[i] contains the minimum time by which course i is completed.
Processing each course from the queue and updating the completion time for its neighboring courses (those that depend on it) by taking the maximum of their current known completion time and the sum of the current course's finishing time and the neighbor’s duration.
The answer is the maximum value in the dp array after processing all courses.

Code Solutions

# Function to calculate minimum time needed to finish all courses
from collections import deque, defaultdict

def minimumTime(n, relations, time):
    # Create the graph and in-degrees array
    graph = defaultdict(list)
    indegree = [0] * (n + 1)
    
    # Build graph and in-degree count from prerequisite relations
    for pre, course in relations:
        graph[pre].append(course)
        indegree[course] += 1

    # dp[i] denotes the earliest month at which course i can be completed.
    dp = [0] * (n + 1)
    
    # Initialize dp for nodes with no prerequisites; course i takes time[i-1] months.
    queue = deque()
    for course in range(1, n + 1):
        if indegree[course] == 0:
            dp[course] = time[course - 1]
            queue.append(course)
    
    # Process courses in topological order
    while queue:
        current = queue.popleft()
        # For all courses that have "current" as prerequisite:
        for next_course in graph[current]:
            # Update the finishing time for next_course: choose maximum between what we have and new route (finish current + time for next)
            dp[next_course] = max(dp[next_course], dp[current] + time[next_course - 1])
            # Decrease indegree since one prerequisite is satisfied
            indegree[next_course] -= 1
            # If all prerequisites are now met, add next_course to the queue
            if indegree[next_course] == 0:
                queue.append(next_course)
    
    # The answer is the maximum finishing time among all courses.
    return max(dp)

# Example usage:
#print(minimumTime(3, [[1,3],[2,3]], [3,2,5]))  # Expected output: 8