Order Tasks with Dependencies Using a Deterministic Topological Sort

Tasks have prerequisite tasks and form a directed acyclic graph. Return a valid execution order in which each task appears after all its prerequisites.

For this exercise, task IDs are integers and ties are resolved by returning the lexicographically smallest valid order. The task-ID representation and tie rule make the dependency-ordering follow-up deterministic.

Function Signature

order_tasks(n: int, dependencies: list[list[int]]) -> list[int]

Input

Tasks are numbered from 0 through n - 1. Each pair [task, prerequisite] means prerequisite must occur before task.

Output

Return all task IDs exactly once in the lexicographically smallest valid order. Lexicographic comparison uses integer values at the first differing position. Return an empty list when n is zero.

Constraints

• 0 <= n <= 100000.
• 0 <= len(dependencies) <= 200000.
• Every referenced task ID is in [0, n).
• There are no repeated dependency pairs or self-dependencies.
• The graph is guaranteed to be acyclic.

Examples

Input: n = 4, dependencies = [[2,0],[2,1],[3,1]]

Output: [0,1,2,3]

Input: n = 4, dependencies = [[0,2],[1,2]]

Output: [2,0,1,3]

Input: n = 3, dependencies = []

Output: [0,1,2]

Input: n = 0, dependencies = []

Output: []

Lexicographically Smallest Task Execution Order

You are scheduling n tasks numbered from 0 through n - 1. Some tasks cannot begin until other tasks have finished.

Each element of dependencies is a pair [task, prerequisite], which means that prerequisite must occur before task. The dependency graph is guaranteed to be acyclic, so at least one valid execution order always exists.

Return a list that contains every task ID from 0 through n - 1 exactly once, ordered so that each task appears after all of its prerequisites. Several valid orders may exist; return the lexicographically smallest one. Lexicographic comparison scans the two orders position by position and prefers the order whose integer value is smaller at the first position where they differ. Return an empty list when n is zero.

Example 1:

Input: n = 4, dependencies = [[2, 0], [2, 1], [3, 1]]
Output: [0, 1, 2, 3]

Explanation: Task 2 must come after tasks 0 and 1, and task 3 must come after task 1. Tasks 0 and 1 are free at the start, and 0 is the smaller of them; after both are placed, tasks 2 and 3 are free and 2 is smaller.

Example 2:

Input: n = 4, dependencies = [[0, 2], [1, 2]]
Output: [2, 0, 1, 3]

Explanation: Tasks 0 and 1 both require task 2, so only tasks 2 and 3 are free at the start. Taking the smaller free task, 2, releases 0 and 1, and the remaining free tasks are then taken in increasing order.

All task IDs fit comfortably in a 32-bit signed integer; no value in the input or the output exceeds 2^31 - 1.

Hints

1. A task may be placed only once every one of its prerequisites has been placed. How many unplaced prerequisites does each task have at the start, and how does that count change as you place tasks?
2. At many steps more than one task is legal. The lexicographic rule compares orders at the first position where they differ, which pins down exactly which of the legal tasks you must place next.
3. Tasks that no pair mentions still belong in the output, and n can be zero.

Approach

Algorithm: Kahn's topological sort driven by a min-heap instead of a plain queue.

1. Build an adjacency list and an in-degree count. The pair [task, prerequisite] contributes the edge prerequisite -> task and increments indegree[task].
2. Push every task whose in-degree is 0 into a min-heap.
3. Repeatedly pop the smallest available task, append it to the answer, then decrement the in-degree of each task that depends on it and push any task whose in-degree reaches 0.

Invariant: at the start of every iteration the heap holds exactly the tasks that are not yet placed and all of whose prerequisites are already placed. Those are precisely the tasks that may legally be placed next, and no others.

Why the greedy choice is optimal: let v be the smallest available task and suppose some valid order O places a different task u first. Every prerequisite of v is already placed, so v can be moved to the front of O without breaking any dependency, and the resulting order is still valid while being smaller at the first differing position. Therefore the lexicographically smallest valid order must begin with the smallest available task. The same argument applies to every remaining suffix, so repeatedly taking the smallest available task yields the lexicographically smallest valid order overall.

Edge cases: n = 0 returns an empty list; an empty dependencies list returns 0, 1, ..., n - 1 because every task starts available; isolated tasks and disconnected components are handled since all in-degree-0 tasks enter the heap up front; a task with several prerequisites is released only when the last of them is placed. The graph is guaranteed acyclic, so the loop always emits all n tasks.

Common wrong approaches: a FIFO queue or a DFS-based topological sort produces a valid order but not necessarily the lexicographically smallest one, and reading the pair as [prerequisite, task] reverses every edge.

• Time complexity: O((n + m) log n), where m = len(dependencies)
• Space complexity: O(n + m)