Show problems as
Classic problem #2050HardArrayDynamic ProgrammingGraph TheoryTopological SortDirected Acyclic Graph

Parallel Courses III

Real-world version: Refinery Shutdown Span
Tracked in this browser only
Read Parallel Courses III on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A refinery shutdown is broken into stages jobs numbered 1 through stages. Job i occupies hours[i - 1] hours from the moment it starts and runs straight through to its finish.

precedes[j] = [a, b] records that job a has to be finished before job b may begin. Each ordered pair appears at most once and the pairs never close a loop.

The crew is large enough that any number of jobs may run side by side, and a job begins at the very moment the last job it waits on has finished. A job with nothing ahead of it begins at hour 0.

Return the number of hours from hour 0 until the final job finishes.

Examples

Example 1

Input
stages = 4, precedes = [[1, 2], [1, 3], [2, 4], [3, 4]], hours = [2, 3, 6, 1]
Output
9

Job 1 runs from hour 0 to hour 2. Jobs 2 and 3 both begin at hour 2 and finish at hours 5 and 8. Job 4 waits on both of them, so it begins at hour 8 and finishes at hour 9.

Example 2

Input
stages = 5, precedes = [], hours = [3, 1, 4, 1, 5]
Output
5

Nothing waits on anything, so all five jobs begin at hour 0 and job 5 is the last to finish, at hour 5.

Example 3

Input
stages = 3, precedes = [[1, 2]], hours = [5, 1, 9]
Output
9

Job 1 runs from hour 0 to hour 5 and job 2 follows from hour 5 to hour 6. Job 3 waits on nothing, so it runs from hour 0 to hour 9.

Constraints

  • 1 <= stages <= 5 * 10^4
  • 0 <= precedes.length <= min(stages * (stages - 1) / 2, 5 * 10^4)
  • precedes[j].length == 2
  • 1 <= a, b <= stages
  • a != b
  • All the pairs [a, b] are unique.
  • hours.length == stages
  • 1 <= hours[i] <= 10^4
  • The pairs never close a loop.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def shutdown_span(stages: int, precedes: list[list[int]], hours: list[int]) -> int:
Java
public int shutdownSpan(int stages, int[][] precedes, int[] hours)

More on the same topics