MANG Problem #48: Parallel Courses III (Hard)

1. Problem Statement

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCourse_j, nextCourse_j], denoting that course prevCourse_j has to be completed before course nextCourse_j starts.

You are also given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)-th course.

You may take any number of courses simultaneously. Return the minimum number of months needed to complete all the courses.

2. Approach: Topological Sort + DP

This problem asks for the longest path (critical path) in a Directed Acyclic Graph (DAG). Since we can take courses in parallel, the start time of a course is determined by the maximum completion time of all its prerequisites.

1. Build Graph: Standard Adjacency List and inDegree array.
2. DP Array: maxTime[i] stores the maximum time required to complete course i (including all its prerequisites). Initialize it with time[i].
3. Kahn's Algorithm:
   • Push all courses with inDegree == 0 to a queue.
   • When processing a course u, look at its neighbors v.
   • The new time to complete v is max(maxTime[v], maxTime[u] + time[v]). Update maxTime[v].
   • Decrement inDegree[v]. If it hits 0, push to queue.
4. Result: Return the maximum value in the maxTime array.

3. Java Implementation

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 + 1];
    for (int[] rel : relations) {
        adj.get(rel[0]).add(rel[1]);
        inDegree[rel[1]]++;
    }
    
    int[] maxTime = new int[n + 1];
    Queue<Integer> q = new LinkedList<>();
    
    // Initialize base cases
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            q.offer(i);
            maxTime[i] = time[i - 1]; // time is 0-indexed
        }
    }
    
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u)) {
            // The time to finish V is the max of its current known time, 
            // or the time to finish U plus V's duration.
            maxTime[v] = Math.max(maxTime[v], maxTime[u] + time[v - 1]);
            
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.offer(v);
            }
        }
    }
    
    int result = 0;
    for (int i = 1; i <= n; i++) {
        result = Math.max(result, maxTime[i]);
    }
    return result;
}

4. 5-Minute "Video-Style" Walkthrough

1. The "Aha!" Moment: If course C depends on course A (takes 10 months) and course B (takes 2 months), you can't start C until month 10. The dependency with the longest duration is the bottleneck.
2. The DP State: maxTime[i] accumulates the bottleneck. Every time an edge U -> V is processed, we check if U's completion time forces V to finish later than we previously thought.
3. The Parallel Processing: Because we use Kahn's algorithm, we are guaranteed that when we pull a course out of the queue, all of its prerequisites have been fully evaluated, so its maxTime is completely finalized.

5. Interview Discussion

• Interviewer: "What is the time complexity?"
• You: "O(V + E) where V is the number of courses and E is the number of dependencies. We visit each course and each dependency edge exactly once."
• Interviewer: "Can this be solved with DFS?"
• You: "Yes, we can use DFS with Memoization. dfs(node) would return the max time to finish that node by recursively taking the max of dfs(neighbor) + time[node]. Both approaches are O(V + E), but BFS (Kahn's) avoids deep recursion stacks."