How should I practice Parallel Courses III?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Parallel Courses III associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Parallel Courses III

Google● HardINTERNONSITE INTERVIEW

Learn

Problem statement

You are given n courses numbered from 1 to n. Each relation [prevCourse, nextCourse] means that prevCourse must be completed before nextCourse can begin.

The array time is zero-indexed, and time[i] is the number of months needed to complete course i + 1. You may begin any number of courses at the same time once all of their prerequisites are complete.

Return the minimum number of months needed to complete all courses.

Function

minimumCourseCompletionTime(n: int, relations: int[][], time: int[]) → int

Examples

Example 1

n = 3relations = [[1,3],[2,3]]time = [3,2,5]return = 8

Courses 1 and 2 start together. Course 3 starts after month 3 and finishes five months later.

Example 2

n = 5relations = [[1,5],[2,5],[3,5],[3,4],[4,5]]time = [1,2,3,4,5]return = 12

The critical prerequisite chain is course 3, then course 4, then course 5, requiring 3 + 4 + 5 = 12 months.

Example 3

n = 2relations = []time = [4,7]return = 7

With no prerequisites, both courses run in parallel, so completion is determined by the slower course.

Constraints

1 <= n <= 50000.
0 <= relations.length <= 50000.
relations[i].length == 2.
1 <= prevCourse, nextCourse <= n.
The prerequisite graph is a directed acyclic graph.
time.length == n.
1 <= time[i] <= 10000.