Earliest Project Finish
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 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
| durations | prereqs | result |
|---|---|---|
[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
-
durations.length,durations[i] -
prereqs.length,a,b,ab; duplicates may appear; no cycles - The answer may exceed 32 bits.
Expected complexity
- Time
- O(N + M)
- Space
- O(N + M)
Examples
| durations | prereqs | Expected |
|---|---|---|
[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 in the worst case and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1646 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 4 | verdict only |