Lv.3graphheaptopological-sort
Task Order
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
There are n tasks 0..n-1; rules[i] = [a, b] means task a must come before task b. Return an order of all tasks that
respects every rule. If several exist, return the lexicographically smallest; if none exists, return [].
Examples
| n | rules | result |
|---|---|---|
4 | [[3, 1], [2, 1], [1, 0]] | [2, 3, 1, 0] |
3 | [[0, 1], [1, 2], [2, 0]] | [] |
3 | [] | [0, 1, 2] |
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(n: int, rules: int[][]) → int[]
Constraints
-
n,rules.length - ; rules may repeat, and
a == bis a contradiction.
Expected complexity
- Time
- O((N + M) log N)
- Space
- O(N + M)
Examples
| n | rules | Expected |
|---|---|---|
4 | [[3,1],[2,1],[1,0]] | [2,3,1,0] |
3 | [[0,1],[1,2],[2,0]] | [] |
3 | [] | [0,1,2] |
Hint
Hint
Kahn's topological sort with a min-heap instead of a queue: always take the smallest task whose in-degree is 0. If fewer than
n tasks come out there is a cycle. Scanning all tasks for the smallest ready one is 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 | 1630 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 | 10 | verdict only |
| performance | 60 | 4 | verdict only |