LeetCode 2050 - Parallel Courses III

The problem asks us to determine the minimum number of months required to complete all courses given prerequisite relationships and the time each course takes. Each course is labeled from 1 to n, and relations describes which courses must be completed before others.

leetcodehardarraydynamic-programminggraph-theorytopological-sort

LeetCode Problem 2050

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Graph Theory, Topological Sort

Solution

Problem Understanding

The problem asks us to determine the minimum number of months required to complete all courses given prerequisite relationships and the time each course takes. Each course is labeled from 1 to n, and relations describes which courses must be completed before others. The time array provides the duration of each course, where time[i] is the time to complete course (i+1).

The key point is that any number of courses can be taken simultaneously, but a course can only start when all its prerequisites are completed. This naturally forms a directed acyclic graph (DAG) of course dependencies, where the goal is to compute the longest path through the graph in terms of cumulative time, since the overall schedule is determined by the slowest chain of dependent courses.

The input constraints tell us that n can be up to 50,000 and relations can be up to 50,000 edges. This immediately rules out brute-force approaches that attempt all course orderings, since the combinatorial possibilities are enormous. Additionally, the graph is guaranteed to be a DAG, so there are no cycles, simplifying the problem to DAG longest-path computation.

Important edge cases include courses with no prerequisites (can start immediately), courses with multiple prerequisites (we must wait for the longest chain), and sparse graphs (no dependencies at all).

Approaches

Brute Force

A naive brute-force approach would try all permutations of course orderings and compute the total time required for each valid ordering, respecting prerequisites. This would correctly produce the minimum total time but is completely infeasible for n = 50,000 because the number of permutations grows factorially, and checking prerequisite validity for each ordering is costly.

Optimal Approach

The optimal approach leverages topological sorting and dynamic programming on a DAG. The idea is to compute, for each course, the earliest time it can be completed. We can perform a topological sort to process courses in order of dependencies. For each course, the earliest completion time is the maximum of the completion times of all its prerequisites plus the time of the current course. Finally, the minimum total months to finish all courses is the maximum completion time across all courses.

This approach is efficient because it processes each course and relation exactly once.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Try all permutations of course orderings
Optimal O(n + m) O(n + m) Topological sort + DP on DAG; m is the number of relations

Algorithm Walkthrough

  1. Initialize Data Structures: Build an adjacency list graph for the DAG where graph[u] contains all courses dependent on u. Also, initialize in_degree array to track prerequisites for each course.
  2. Topological Queue: Initialize a queue with courses that have no prerequisites (in_degree == 0), since these can start immediately.
  3. DP Array: Create a dp array of size n+1 to store the earliest completion time for each course. For courses without prerequisites, set dp[course] = time[course-1].
  4. Process Queue: While the queue is not empty, pop a course u, and for each dependent course v in graph[u], update dp[v] = max(dp[v], dp[u] + time[v-1]) to account for the longest prerequisite chain. Decrease in_degree[v] by 1, and if it reaches 0, push v into the queue.
  5. Result: After processing all courses, the answer is max(dp[1:]), the longest completion time among all courses.

Why it works: The algorithm ensures that each course's completion time accounts for the maximum time of all its prerequisites. By processing in topological order, we guarantee that every course is considered only after all its prerequisites are handled.

Python Solution

from collections import deque
from typing import List

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        graph = [[] for _ in range(n + 1)]
        in_degree = [0] * (n + 1)
        
        for u, v in relations:
            graph[u].append(v)
            in_degree[v] += 1
        
        dp = [0] * (n + 1)
        queue = deque()
        
        for course in range(1, n + 1):
            if in_degree[course] == 0:
                dp[course] = time[course - 1]
                queue.append(course)
        
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                dp[v] = max(dp[v], dp[u] + time[v - 1])
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    queue.append(v)
        
        return max(dp[1:])

Implementation Explanation: We first build the graph and count prerequisites for each course. Courses with no prerequisites start immediately. Using a queue for topological sorting ensures that we process courses only after all prerequisites. For each course, we dynamically calculate its earliest completion time. Finally, the maximum in the dp array gives the total minimum months.

Go Solution

package main

func minimumTime(n int, relations [][]int, time []int) int {
    graph := make([][]int, n+1)
    inDegree := make([]int, n+1)
    
    for _, rel := range relations {
        u, v := rel[0], rel[1]
        graph[u] = append(graph[u], v)
        inDegree[v]++
    }
    
    dp := make([]int, n+1)
    queue := []int{}
    
    for course := 1; course <= n; course++ {
        if inDegree[course] == 0 {
            dp[course] = time[course-1]
            queue = append(queue, course)
        }
    }
    
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        for _, v := range graph[u] {
            if dp[v] < dp[u]+time[v-1] {
                dp[v] = dp[u] + time[v-1]
            }
            inDegree[v]--
            if inDegree[v] == 0 {
                queue = append(queue, v)
            }
        }
    }
    
    maxTime := 0
    for _, t := range dp[1:] {
        if t > maxTime {
            maxTime = t
        }
    }
    return maxTime
}

Go Notes: The Go solution mirrors Python closely. Slices handle dynamic adjacency lists. Queue operations are done using slice manipulation. The DP updates use a simple comparison instead of max function.

Worked Examples

Example 1

Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5]

Step by step:

  1. Graph: {1:[3], 2:[3], 3:[]}, in_degree = [0,0,0,2]
  2. Queue starts with [1,2]
  3. DP: [0,3,2,0]
  4. Process 1: update dp[3] = max(0,3+5)=8
  5. Process 2: update dp[3] = max(8,2+5)=8
  6. dp array = [0,3,2,8], max = 8 → Output: 8

Example 2

Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]

Step by step:

  1. Graph: {1:[5],2:[5],3:[5,4],4:[5],5:[]}, in_degree=[0,0,0,0,1,4]
  2. Queue: [1,2,3], dp: [0,1,2,3,0,0]
  3. Process 1: dp[5] = 1+5=6
  4. Process 2: dp[5] = max(6,2+5)=7
  5. Process 3: dp[4]=3+4=7, dp[5]=max(7,3+5)=8
  6. Process 4: dp[5]=max(8,7+5)=12
  7. Process 5 done. max(dp)=12 → Output: 12

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Each course and relation is processed once during topological sort
Space O(n + m) Graph adjacency list O(m), DP array O(n), queue O(n)

The algorithm scales linearly with the number of courses and relations, which is efficient for the given constraints.

Test Cases

# Provided examples
assert Solution().minimumTime(3, [[1,3],[2,3]], [3,2,5]) == 8
assert Solution().minimumTime(5, [[1,5],[2,5],[3,5],[3,4],[4,5]], [1,2,3,4,5]) == 12

#