Parallel Stages & Critical Path

The problem, from first principles

Tasks that do not depend on each other can run at the same time, and an agent that runs independent tool calls in parallel finishes much sooner. Grouping a DAG into stages makes this explicit: stage 0 holds tasks with no dependencies, stage 1 holds tasks whose dependencies are all in stage 0, and so on, so every task in a stage can run concurrently. How fast the whole plan can possibly finish is limited by the critical path, the longest chain of dependent tasks measured by duration. No amount of parallel hardware beats it, so it tells you which task to speed up first.

From theory to code

Implement parallel_stages and critical_path_length.

Constraints

• tasks maps each task to its dependency list and is guaranteed to be a valid DAG.
• parallel_stages(tasks) returns a list of stages. A task's stage index is 0 if it has no dependencies, else 1 + max(stage of its dependencies). Each stage is a list of task names sorted alphabetically; stages are in increasing order.
• critical_path_length(tasks, durations) is the largest total duration over all dependency chains, where durations[name] is the time of that task. Return a float (0.0 for an empty plan).

Hints