FastPrep
Problem · Graph

Minimum Time to Complete Target Courses

Learn this problem
● MediumMeta logoMetaFULLTIMEONSITE INTERVIEW
See Meta hiring insights

Problem statement

There are n courses labeled from 0 through n - 1. Course i takes durations[i] time units.

Each pair [course, prerequisite] in prerequisites means the prerequisite must finish before the course can start. The prerequisite graph is acyclic.

You may take any number of available courses in parallel. Return the minimum time needed to finish every course in targets, including every transitive prerequisite needed by those targets. Courses outside that required closure do not affect the answer.

Function

minimumTimeForTargets(durations: int[], prerequisites: int[][], targets: int[]) → long

Examples

Example 1

durations = [3,2,5]prerequisites = [[2,0],[2,1]]targets = [2]return = 8

Courses 0 and 1 run in parallel. Course 2 starts at time 3 and finishes at time 8.

Example 2

durations = [2,4,3,7]prerequisites = [[1,0],[2,0]]targets = [1,2]return = 6

After course 0 finishes at time 2, courses 1 and 2 run together. The slower target finishes at time 6. Disconnected course 3 is irrelevant.

Example 3

durations = [5,1,2]prerequisites = []targets = [1,2]return = 2

With no prerequisites, both targets start immediately and the later one finishes after 2 time units.

Constraints

  • 1 <= durations.length <= 100000.
  • 1 <= durations[i] <= 10^9.
  • 0 <= prerequisites.length <= 200000.
  • Every prerequisite pair contains distinct valid course labels, all pairs are unique, and the graph is acyclic.
  • 1 <= targets.length <= durations.length, and target labels are unique.
  • The answer fits a signed 64-bit integer.

More Meta problems

drafts saved locally
public long minimumTimeForTargets(int[] durations, int[][] prerequisites, int[] targets) {
    // Write your code here.
}
durations[3,2,5]
prerequisites[[2,0],[2,1]]
targets[2]
expected8
checking account