Funcia
Lv.3dagdpgraphtopological-sort

Earliest Project Finish

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

A project consists of N tasks numbered 0 to N - 1; task i takes durations[i] days. prereqs[j] = [a, b] means task b can start only after task a has finished.

There are enough workers: a task starts as soon as all of its prerequisites are done, and any number of tasks may run in parallel. The project starts at time 0. Return the earliest time at which every task is finished. The prerequisites contain no cycle.

Examples

durationsprereqsresult
[3, 2, 4, 1][[0, 2], [1, 2], [2, 3]]8
[5, 1, 1, 1][[1, 2], [2, 3]]5
[2, 2, 2][]2

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(durations: int[], prereqs: int[][]) → long

Constraints

  • 1≤N=1 \le N = durations.length ≤200,000\le 200{,}000, 1≤1 \le durations[i] ≤10,000\le 10{,}000
  • 0≤M=0 \le M = prereqs.length ≤200,000\le 200{,}000, 0≤0 \le a, b <N< N, a ≠\ne b; duplicates may appear; no cycles
  • The answer may exceed 32 bits.

Expected complexity

Time
O(N + M)
Space
O(N + M)

Examples

durationsprereqsExpected
[3,2,4,1][[0,2],[1,2],[2,3]]8
[5,1,1,1][[1,2],[2,3]]5
[2,2,2][]2

Hint

Hint

finish[v] = durations[v] + max(finish[u]) over prerequisites u (0 if none); the answer is the largest finish, the longest weighted path in the DAG. Compute it in topological order (Kahn's queue of in-degree-0 tasks). Re-scanning all prerequisites until nothing changes is O(N⋅M)O(N \cdot M) in the worst case and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251646 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.