Given a DAG as deps (task → list of prerequisites) and max_parallel worker slots, schedule the tasks into waves. A task can run in a wave once all of its prerequisites ran in earlier waves, and each wave runs at most max_parallel tasks.
When more tasks are ready than there are slots, fill the slots critical-path first: prefer the task with the greatest height — the number of tasks on the longest dependency chain from it to the end of the DAG, counting itself (a task nothing depends on has height 1). Break ties alphabetically. Ready tasks that don't get a slot wait and compete again in the next wave alongside tasks that just became ready.
Return the list of waves, each sorted alphabetically. Include tasks that appear only as prerequisites. If the graph has a cycle anywhere, return None.
What the tests check
6 on Run · 7 on Submit01a cap at least as wide as the DAG gives the plain waves
02the cap spills ready tasks into the next wave
03the longest remaining chain gets a slot first
04priority is chain length still ahead, not fan-out or descendant count
05tasks left waiting compete with newly ready ones
06prereq-only tasks are included
Submit runs these and one more check you don’t see, so code written for the visible tests alone can still miss.