Order Tasks with Dependencies Using a Deterministic Topological Sort

Problem Statement

You are building a build system that must execute a set of tasks according to their prerequisites. You are given a list of unique task names tasks and a list of directed dependencies dependencies, where each dependency is a pair [prereq, task], indicating that prereq must be executed before task.

Return a list of all task names in a valid execution order such that:

1. Every task appears exactly once.
2. For every dependency [prereq, task], prereq appears before task in the output.
3. Whenever multiple tasks are simultaneously ready to run, the task with the lexicographically smallest name is chosen first.
4. Disconnected tasks (tasks with no incoming or outgoing dependencies) are also included in the schedule according to the same rules.

If the dependency graph contains a cycle and no valid topological order is possible, return an empty list [].

Function Signature

def order_tasks(tasks: list[str], dependencies: list[list[str]]) -> list[str]:
    pass

Examples

Example 1

Input: 
tasks = ["build", "test", "lint", "deploy"]
dependencies = [["lint", "test"], ["build", "test"], ["test", "deploy"]]

Output: ["build", "lint", "test", "deploy"]
Explanation:
- Initially, both "build" and "lint" have 0 unmet prerequisites.
- Lexicographically, "build" comes before "lint", so "build" is executed first.
- Next, "lint" is executed.
- Now, "test" has all prerequisites satisfied and executes.
- Finally, "deploy" executes.

Example 2

Input:
tasks = ["zeta", "alpha", "beta"]
dependencies = []

Output: ["alpha", "beta", "zeta"]
Explanation: No dependencies exist, so tasks are scheduled in lexicographical order.

Constraints

• 1 <= len(tasks) <= 20,000
• 0 <= len(dependencies) <= 50,000
• Each task name consists of 1 to 20 lowercase English letters.
• All names in tasks are unique.
• In each dependency [u, v], both u and v are guaranteed to belong to tasks and u != v.
• Dependencies may contain duplicate pairs.