Group dependent tasks into parallel levels

This is topological sorting with one extra requirement: the answer is grouped into levels. Level 0 holds every task with no prerequisites. Level k holds every task whose prerequisites are all in levels 0..k-1, and at least one of them is in level k-1. Put another way, a task's level is the length of the longest dependency chain that ends at it. All tasks in one level can run in parallel. Within a level, tasks are listed in lexicographic order so the output is deterministic.

Brute force. Repeat rounds: scan every task that hasn't been scheduled, collect those whose prerequisites are all scheduled, sort that set, and emit it as the next level. Stop when a round finds nothing. If tasks remain at that point, there is a cycle. This costs O(V · (V + E)) in the worst case (a chain of V tasks needs V rounds, and each round rescans everything). It is a fine thing to say out loud, but don't code it.

Optimal: Kahn's algorithm, one frontier at a time.

1. Build an adjacency list from -> [to] and an in-degree count for every task. Register tasks that appear only in dependencies too, and ignore exact duplicate edges so in-degrees stay correct.
2. The first frontier is every task with in-degree 0, sorted.
3. While the frontier isn't empty: append it as a level. For each task in it, decrement the in-degree of each successor. A successor whose count reaches 0 joins the next frontier. Sort the next frontier and continue.
4. If fewer tasks were emitted than exist, some tasks are stuck on a cycle. Return [].

Why it works. A task's in-degree reaches 0 exactly when its last remaining prerequisite is processed. Its prerequisites live in levels < k, and the last of them is in level k-1, so it is released while level k-1 is processed and lands in level k. That is the longest-chain definition. Tasks on a cycle, or downstream of one, never reach in-degree 0, which is how we detect cycles.

Invariants.

• Every task in the current frontier has all its prerequisites in earlier levels.
• Each task enters a frontier at most once, because its in-degree drops to 0 only once.
• sum(len(level)) == number of tasks exactly when the graph is acyclic.

Sorting each frontier, instead of using one global min-heap, is what keeps the levels intact. A single heap gives the lexicographically smallest flat order, which is a different question and a common follow-up.

from collections import defaultdict


def schedule_levels(tasks: list[str], dependencies: list[list[str]]) -> list[list[str]]:
    """Group tasks into levels that can run in parallel.

    dependencies[i] = [before, after] means `before` must finish before `after`
    starts. Each level is sorted lexicographically. Returns [] on a cycle.
    """
    successors: dict[str, set[str]] = defaultdict(set)
    indegree: dict[str, int] = {t: 0 for t in tasks}

    for before, after in dependencies:
        indegree.setdefault(before, 0)
        indegree.setdefault(after, 0)
        if before == after:
            return []  # a task that depends on itself can never start
        if after not in successors[before]:  # skip duplicate edges
            successors[before].add(after)
            indegree[after] += 1

    frontier = sorted(t for t, d in indegree.items() if d == 0)
    levels: list[list[str]] = []
    scheduled = 0

    while frontier:
        levels.append(frontier)
        scheduled += len(frontier)
        released: list[str] = []
        for task in frontier:
            for nxt in successors[task]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    released.append(nxt)
        frontier = sorted(released)

    return levels if scheduled == len(indegree) else []


def schedule_flat(tasks: list[str], dependencies: list[list[str]]) -> list[str]:
    """Course Schedule II style answer: one valid order, flattened by level."""
    return [t for level in schedule_levels(tasks, dependencies) for t in level]


if __name__ == "__main__":
    assert schedule_levels(
        ["build", "deploy", "fetch", "lint", "test"],
        [["fetch", "build"], ["fetch", "lint"], ["build", "test"],
         ["lint", "test"], ["test", "deploy"]],
    ) == [["fetch"], ["build", "lint"], ["test"], ["deploy"]]
    # Longest chain decides the level, not the shortest.
    assert schedule_levels(
        ["a", "b", "c"], [["a", "b"], ["b", "c"], ["a", "c"]]
    ) == [["a"], ["b"], ["c"]]
    assert schedule_levels(["x", "y"], [["x", "y"], ["y", "x"]]) == []
    assert schedule_levels(["solo"], []) == [["solo"]]
    assert schedule_levels([], []) == []
    assert schedule_levels(["m", "k", "z"], []) == [["k", "m", "z"]]
    assert schedule_levels(["a", "b"], [["a", "b"], ["a", "b"]]) == [["a"], ["b"]]
    assert schedule_levels(["a"], [["a", "a"]]) == []
    # Cycle downstream of a valid part still means no schedule.
    assert schedule_levels(["a", "b", "c"], [["a", "b"], ["b", "c"], ["c", "b"]]) == []
    assert schedule_flat(["b", "a"], [["b", "a"]]) == ["b", "a"]
    print("ok")

Let V be the number of tasks, E the number of dependencies and L the maximum task-name length.

• Building the graph: O(V + E) set and dict operations, each O(L) to hash a name.
• Processing frontiers: every task enters exactly one frontier and every edge is relaxed once, so O(V + E).
• Sorting frontiers: the frontiers partition the tasks, so the total is O(Σ kᵢ log kᵢ) ⊆ O(V log V) comparisons, each up to O(L).
• Overall: O((V log V + E) · L) time, O(V + E) space for the graph, in-degrees and output.

• tasks = ["build","deploy","fetch","lint","test"], deps fetch→build, fetch→lint, build→test, lint→test, test→deploy → [["fetch"], ["build","lint"], ["test"], ["deploy"]].
• Diamond with a shortcut: a→b, b→c, a→c → [["a"], ["b"], ["c"]]. c sits at level 2, after its longest chain, not at level 1.
• No dependencies: ["m","k","z"] → [["k","m","z"]], one level, sorted.
• Single task, no deps: ["solo"] → [["solo"]].
• Empty input: [], [] → [].
• Two-task cycle: x→y, y→x → [].
• Self-dependency: a→a → [].
• Cycle downstream of a valid prefix: a→b, b→c, c→b → []. a alone is not a valid full schedule.
• Duplicate edge: a→b listed twice → [["a"], ["b"]], not a hang caused by in-degree 2.
• Task named only in dependencies (if the interviewer allows it): it's registered automatically and scheduled like any other.
• Several independent chains: a→b, c→d→e → [["a","c"], ["b","d"], ["e"]].

1. Return one flat order (Course Schedule II). Flatten the levels (schedule_flat). If they want the lexicographically smallest flat order instead, replace the per-level sort with one min-heap over all ready tasks: pop the smallest, release its successors into the same heap. That is O((V + E) log V) and can interleave levels.
2. Tasks have durations. What is the minimum total time with unlimited workers? Compute finish[t] = duration[t] + max(finish[p] for p in prereqs) in topological order. The answer is max(finish), which is the critical path. Keep parent pointers to print that path.
3. Only k workers. Levels no longer give the schedule directly. Simulate time with an event heap of running tasks and a ready queue: whenever a worker is free, start the next ready task (smallest name, or longest remaining critical path as a heuristic). Optimal k-worker scheduling is NP-hard in general, so say what the greedy rule optimizes.
4. Report the cycle, not just []. Run a three-color DFS on the tasks that were never scheduled. A back edge to a gray node gives the cycle, which you rebuild from the DFS stack. Return it so the caller can see what to fix.
5. Dependencies change at run time (add an edge, or a task finishes). Keep indegree and successors as live state. complete(task) releases successors into the ready set in O(out-degree). add_dependency(a, b) must reject the edge if b can already reach a, which a DFS from b checks. Return the current ready set in sorted order on demand.

Mid-level (L4)

• Recognizes topological sort and builds the adjacency list and in-degrees correctly.
• Gets the level grouping right by processing the frontier as a batch instead of one queue pop at a time.
• Detects cycles by comparing the emitted count with the task count, and handles the empty and no-dependency cases.

Senior (L5)

• Explains why a task lands at its longest-chain depth, and why one global heap breaks the levels.
• Handles duplicate edges, self-loops and tasks that appear only in dependencies without being told.
• States complexity precisely, including the sorting cost and that it's bounded by V log V in total.
• Moves quickly to durations and the critical path, and writes it on the same skeleton.

Staff (L6+)

• Frames levels as parallel execution stages and discusses limited workers: why it's NP-hard, and which greedy rules (critical path first) work well in practice.
• Designs the incremental, long-running version: live in-degree state, rejecting edges that would form a cycle, and reporting the offending cycle.
• Talks about production concerns for a workflow scheduler: failed or retried tasks, partial reruns of only the affected downstream subgraph, and keeping the output deterministic for reproducible runs.