Parallel Courses III

Parallel Courses III

What is this problem about?

The Parallel Courses III problem adds time costs: each course i takes time[i] months. Prerequisites must be completed before starting the next course. Find the minimum total time to complete all courses. This is the critical path problem on a DAG — find the longest weighted path. The array, graph, topological sort, and dynamic programming interview pattern is the core.

Why is this asked in interviews?

Citadel, Stripe, Snowflake, Amazon, TikTok, and Google ask this because it's the classic critical path method (CPM) problem used in project management. The minimum completion time = the longest weighted dependency chain. Topological sort with DP computes this efficiently.

Algorithmic pattern used

Topological sort + DP. dp[i] = earliest completion time for course i = time[i] + max(dp[prereq] for all prereqs of i). Process courses in topological order. Answer = max(dp[i]) for all i.

Example explanation

n=3, relations=[(1,3),(2,3)], time=[3,2,5]. (Course 1 is prereq of 3, course 2 is prereq of 3.) dp[1]=3, dp[2]=2. dp[3]=5+max(3,2)=5+3=8. Answer = max(3,2,8) = 8.

n=5, relations=[(1,5),(2,5),(3,5)], time=[1,2,3,4,5]. dp[1]=1,dp[2]=2,dp[3]=3,dp[4]=4. dp[5]=5+max(1,2,3)=8. Answer=max(1,2,3,4,8)=8.

Common mistakes candidates make

• Using time[i] without adding the max predecessor completion time.
• Not processing in topological order (must complete prerequisites first).
• Taking min instead of max of predecessor times.
• Not handling courses with no prerequisites correctly (dp[i] = time[i]).

Interview preparation tip

Critical path DP is essential for project scheduling problems. The DP recurrence: dp[i] = time[i] + max(dp[prereqs]). This is "longest path in a weighted DAG" — the dual of shortest path but computed via DP on topological order. Practice this on all "minimum time with dependencies" variants. It directly applies to build systems, CI/CD pipelines, and manufacturing scheduling.