Time Complexity Analysis

The time complexity of this approach is exponential in the worst case. Without memoization (caching results), the algorithm re-evaluates the completion time for the same shared prerequisites multiple times. In a dense graph where many courses share the same dependencies, the number of recursive calls explodes, leading to a Time Limit Exceeded (TLE) error.

Core Insight for Parallel Courses III

The core intuition for the optimal solution lies in how we determine the start time of a specific course. If Course C depends on Course A (duration 3) and Course B (duration 5), we cannot start Course C until both A and B are finished. Since A finishes at month 3 and B finishes at month 5, Course C must wait until month 5.

Therefore, the completion time of any node $v$ is: $\text{completion}[v] = \text{time}[v] + \max(\text{completion}[u] \mid \forall u \to v)$

We need to process the nodes in an order such that when we calculate the time for node $v$, the completion times for all its prerequisites ($u$) have already been finalized. Kahn's Algorithm guarantees this order by maintaining the in-degree (number of incoming edges) for each node.

Visual Description: Imagine the graph traversal as a wave moving from independent courses to dependent ones.

1. Initially, courses with an in-degree of 0 (no prerequisites) are "ready." Their completion time is simply their duration.
2. When we "complete" a course $u$, we traverse to its neighbors (courses $v$ that depend on $u$).
3. We update the potential completion time of $v$ using the completion time of $u$.
4. We effectively remove the edge $u \to v$ by decrementing $v$'s in-degree.
5. Once $v$'s in-degree reaches 0, we know we have processed all its prerequisites. The maximum time accumulated so far is the true earliest start time for $v$. We then add $v$ to the queue to propagate its time to its own neighbors.

Algorithm Strategy: Graph BFS - Topological Sort (Kahn's Algorithm)

1. Graph Representation: Construct an adjacency list to represent the graph where adj[u] contains all courses v such that u is a prerequisite for v.
2. In-Degree Calculation: Maintain an array indegree of size $n$, where indegree[i] stores the number of prerequisites for course $i$.
3. Completion Time Tracking: Create an array maxTime initialized such that maxTime[i] = time[i]. This array tracks the earliest possible month course $i$ can be completed. Initially, it assumes no prerequisites.
4. Queue Initialization: Push all nodes with indegree == 0 into a queue. These are the courses that can be started immediately.
5. BFS Traversal:
   • Dequeue a course u.
   • Iterate through all neighbors v (courses that depend on u).
   • Relaxation Step: Update maxTime[v]. The new potential completion time for v is maxTime[u] + time[v]. We take the maximum of its current value and this new value: maxTime[v] = max(maxTime[v], maxTime[u] + time[v]).
   • Decrement indegree[v].
   • If indegree[v] becomes 0, all prerequisites for v have been processed. Enqueue v.
6. Result: After processing all nodes, the answer is the maximum value in the maxTime array.

Execution Flow

Let's trace the algorithm with Example 1: n = 3, relations = [[1,3],[2,3]], time = [3,2,5].

1. Build Graph:

   • Edges: $1 \to 3$, $2 \to 3$.
   • In-degrees: Node 1: 0, Node 2: 0, Node 3: 2.
   • maxTime array initialized to durations: [3, 2, 5] (using 1-based indexing for clarity).

2. Initialize Queue:

   • Nodes 1 and 2 have in-degree 0.
   • Queue: [1, 2].

3. Process Node 1:

   • Pop 1. Neighbor is 3.
   • Update Node 3: maxTime[3] = max(5, maxTime[1] + time[3]) $\to$ max(5, 3 + 5) = 8.
   • Decrement in-degree of 3. New in-degree: 1.
   • In-degree is not 0, do not enqueue 3.
   • Queue: [2].

4. Process Node 2:

   • Pop 2. Neighbor is 3.
   • Update Node 3: maxTime[3] = max(8, maxTime[2] + time[3]) $\to$ max(8, 2 + 5) = 8.
   • Decrement in-degree of 3. New in-degree: 0.
   • In-degree is 0, enqueue 3.
   • Queue: [3].

5. Process Node 3:

   • Pop 3. No neighbors.
   • Queue: [].

6. Final Result:

   • Max value in maxTime is 8.

Proof of Correctness

The correctness relies on the invariant of Kahn's Algorithm: a node is processed (added to the queue) only when its in-degree reaches zero. In the context of this problem, "in-degree zero" implies that all prerequisite courses $u$ for the current course $v$ have been fully processed.

Because we process prerequisites first, the value maxTime[u] correctly represents the earliest finish time for prerequisite $u$. When we update maxTime[v] = max(maxTime[v], maxTime[u] + time[v]), we are strictly adhering to the constraint that $v$ cannot start until the slowest prerequisite finishes. Since the graph is a DAG, every node will eventually reach an in-degree of 0 and be processed exactly once, ensuring the global maximum is found efficiently.

Reference Implementation

C++ Solution for LeetCode 2050

cpp
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        // Build adjacency list and in-degree array
        // Note: Input is 1-indexed, we will convert to 0-indexed logic
        vector<vector<int>> adj(n);
        vector<int> indegree(n, 0);
        
        for (const auto& rel : relations) {
            int prev = rel[0] - 1;
            int next = rel[1] - 1;
            adj[prev].push_back(next);
            indegree[next]++;
        }
        
        // maxTime[i] stores the earliest completion time for course i
        // Initialize with the course's own duration
        vector<int> maxTime(n);
        for (int i = 0; i < n; i++) {
            maxTime[i] = time[i];
        }
        
        // Queue for Kahn's Algorithm (Topological Sort)
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (int v : adj[u]) {
                // Update completion time for neighbor v
                // v can finish only after u finishes + v's own duration
                maxTime[v] = max(maxTime[v], maxTime[u] + time[v]);
                
                indegree[v]--;
                if (indegree[v] == 0) {
                    q.push(v);
                }
            }
        }
        
        // The answer is the maximum completion time among all courses
        int result = 0;
        for (int t : maxTime) {
            result = max(result, t);
        }
        
        return result;
    }
};

Java Solution for LeetCode 2050

java
import java.util.*;

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        
        int[] indegree = new int[n];
        for (int[] rel : relations) {
            int prev = rel[0] - 1;
            int next = rel[1] - 1;
            adj.get(prev).add(next);
            indegree[next]++;
        }
        
        // maxTime tracks completion time. Initialize with course duration.
        int[] maxTime = new int[n];
        for (int i = 0; i < n; i++) {
            maxTime[i] = time[i];
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while (!queue.isEmpty()) {
            int u = queue.poll();
            
            for (int v : adj.get(u)) {
                // Determine max time to complete v based on prerequisite u
                maxTime[v] = Math.max(maxTime[v], maxTime[u] + time[v]);
                
                indegree[v]--;
                if (indegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        
        int result = 0;
        for (int t : maxTime) {
            result = Math.max(result, t);
        }
        
        return result;
    }
}

Python Solution for LeetCode 2050

python
from collections import deque, defaultdict

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        adj = defaultdict(list)
        indegree = [0] * n
        
        # Build graph (convert 1-indexed input to 0-indexed)
        for prev_course, next_course in relations:
            adj[prev_course - 1].append(next_course - 1)
            indegree[next_course - 1] += 1
            
        # Initialize max_time with the base duration of each course
        max_time = list(time)
        
        queue = deque()
        for i in range(n):
            if indegree[i] == 0:
                queue.append(i)
                
        while queue:
            u = queue.popleft()
            
            for v in adj[u]:
                # Update neighbor's completion time
                max_time[v] = max(max_time[v], max_time[u] + time[v])
                
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)
                    
        return max(max_time)