Schedule a bounded DAG

Intermediate50 min

Implement schedule_waves(dependencies, capacity). All task names are strings. Each dictionary value lists that task's prerequisites. At each wave, select at most capacity currently ready tasks in lexical order, then consider them complete together. Reject an unknown dependency, a cycle, or capacity below one. Return a list of waves. Duplicate edges are harmless. This deliberately models barrier-based waves; a real asynchronous scheduler can start a newly ready task before unrelated work in the previous wave finishes.

Your task

Complete the starter function using the contract above.
Use the examples and visible tests to check normal inputs, boundaries, and rejected inputs.
Run tests to record your result, then compare with the explained reference solution.

Examples

EXAMPLE 1

Input{a:[], b:[a], c:[a], d:[b,c]}, capacity=2

Output[[a],[b,c],[d]]

The join runs after both predecessors.

EXAMPLE 2

Input{a:[],b:[],c:[]}, capacity=2

Output[[a,b],[c]]

Only two tasks fit in the first wave.

def schedule_waves(dependencies, capacity):
    raise NotImplementedError