FastPrep
Problem · Graph

Parallel Courses III

Learn this problem
● HardSnowflake logoSnowflakeFULLTIMEONSITE INTERVIEW
See Snowflake hiring insights

Problem statement

There are n courses labeled from 1 through n. You are given prerequisite relations and the duration of every course.

Each relation [previous, next] means course previous must be completed before course next can start. Course i takes time[i - 1] months.

You may take any number of courses concurrently whenever all of their prerequisites are complete. Return the minimum number of months needed to complete every course.

Function

minimumTime(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, when both prerequisites are complete, and finishes five months later at month 8.

Example 2

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

The critical chain is course 3, then course 4, then course 5, with total duration 3 + 4 + 5 = 12.

Constraints

  • 1 <= n <= 5 * 10^4
  • 0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10^4)
  • Every relation contains two distinct course labels between 1 and n.
  • All relations are unique, and the prerequisite graph is acyclic.
  • time.length == n
  • 1 <= time[i] <= 10^4

More Snowflake problems

drafts saved locally
public int minimumTime(int n, int[][] relations, int[] time) {
    // Write your code here.
}
n3
relations[[1,3],[2,3]]
time[3,2,5]
expected8
checking account