Group dependent tasks into parallel levels

You run a build system. Each task has a unique, non-empty lowercase name. Some tasks depend on others: a dependency [before, after] means before must finish before after can start.

Tasks that have no unfinished prerequisites can run at the same time. Group the tasks into levels:

• Level 0 contains every task with no prerequisites.
• A task belongs to level k when all its prerequisites are in levels below k and at least one of them is in level k - 1.

Implement:

def schedule_levels(tasks: list[str], dependencies: list[list[str]]) -> list[list[str]]:
    ...

Return the levels in order. Sort the tasks inside each level lexicographically. If the dependencies contain a cycle, so that no valid schedule exists, return an empty list.

Constraints

• 0 <= len(tasks) <= 10^4, 0 <= len(dependencies) <= 5 * 10^4
• Task names are unique, lowercase, and at most 20 characters.
• Every name in dependencies appears in tasks. A pair may appear more than once.

Example 1

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

build and lint both wait only on fetch, so they share level 1. test needs both of them.

Example 2

tasks = ["a", "b", "c"]
dependencies = [["a", "b"], ["b", "c"], ["a", "c"]]
output: [["a"], ["b"], ["c"]]

c depends directly on a, but it also waits on b, so it goes in level 2.

Example 3

tasks = ["x", "y"]
dependencies = [["x", "y"], ["y", "x"]]
output: []

Reconstructed from the reported question; details may differ from what interviewers ask.