📘

Schedule Parallel-Safe Tool Calls into Waves

Problem Statement

When a model emits several tool calls in one turn, firing them all concurrently is the whole point - but only some of them are actually safe to run together. Two calls that read the same file are fine. A read racing a write on that file is not, and neither is a call that needs the output of another.

Write the scheduler that packs a batch of tool calls into the fewest safe waves.

Background

Each call declares the resource it touches (a file path, a table, an API namespace) and its mode, either "read" or "write". Two calls in the same wave conflict when they name the same resource and at least one of them is a write. Read/read never conflicts - that is the parallelism you are trying to harvest.

Calls may also declare depends_on, a list of call ids whose results they consume. A dependency must complete in a strictly earlier wave.

The scheduler is greedy and order-sensitive, which keeps it deterministic:

Walk the still-unscheduled calls in their original order.
Skip any call whose dependencies are not all already completed in an earlier wave - it waits.
Otherwise, add it to the current wave if it conflicts with nothing already placed in this wave; if it does conflict, it waits.
Close the wave, mark its calls complete, repeat with the calls that waited.

If a pass places no calls at all, the batch is unschedulable - a dependency cycle, or a dependency on an id that is not in the batch.

Your Task

Implement:

def plan_parallel_waves(calls):

calls: list of dicts {"id": str, "tool": str, "resource": str, "mode": "read"|"write", "depends_on": list[str]}. depends_on may be absent, meaning no dependencies.

Return list[list[str]] - one inner list per wave, holding that wave's call ids sorted ascending. Return [] if the batch is unschedulable.

Input/Output Format

Returns a list of lists of strings. Note the greedy packing uses the original order, but each wave is reported sorted.

Sample

calls = [
    {"id": "c1", "tool": "read_file",  "resource": "cfg", "mode": "read"},
    {"id": "c2", "tool": "read_file",  "resource": "cfg", "mode": "read"},
    {"id": "c3", "tool": "write_file", "resource": "cfg", "mode": "write"},
]
print(plan_parallel_waves(calls))
# [['c1', 'c2'], ['c3']]

c1 and c2 both only read cfg, so they share a wave; c3 writes it and is pushed to the next.

Example:

Input:

calls = [{'id':'c1','tool':'read_file','resource':'cfg','mode':'read'},{'id':'c2','tool':'read_file','resource':'cfg','mode':'read'},{'id':'c3','tool':'write_file','resource':'cfg','mode':'write'}]
print(plan_parallel_waves(calls))

Output:

[['c1', 'c2'], ['c3']]

Reasoning:

Wave 1 starts with c1 (read cfg). c2 also only reads cfg, so read/read is safe and it joins. c3 writes cfg, which conflicts with both reads already in the wave, so it waits. Wave 2 contains c3 alone.

Constraints:

0 <= len(calls) <= 300; ids are unique strings
mode is "read" or "write"; depends_on defaults to []
Conflict rule: same resource and at least one write
A dependency must land in a strictly earlier wave, never the same one
Greedy packing walks the unscheduled calls in their original order
Each wave is reported with its ids sorted ascending
Return [] when no progress is possible (cycle or missing dependency id)
An empty input returns []

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAHard Bootstrap Confidence Interval Width for Eval AccuracyMedium Route to the Cheapest Model Meeting QualityMedium pass@k EstimatorMedium Savings from a Semantic CacheMedium

1. Background Knowledge

This problem models resource contention and dependency resolution in parallel execution systems. In distributed computing and AI agent orchestration, tasks often compete for shared resources (files, database rows, API quotas). The core constraint here is that read-write and write-write operations on the same resource are mutually exclusive, while read-read operations are safe to parallelize. This is a simplified version of concurrency control mechanisms like Optimistic Concurrency Control or Two-Phase Locking, where the scheduler must ensure data consistency without deadlocks.

The problem also involves topological sorting concepts. Dependencies define a partial order among tasks. If task $A$ depends on task $B$ , $B$ must appear in an earlier wave. This creates a directed acyclic graph (DAG) structure. If cycles exist (e.g., $A$ depends on $B$ and $B$ depends on $A$ ), the system is unschedulable. The "greedy" nature of the scheduler means we don't look for the globally optimal minimal waves (which is NP-hard in general graph coloring), but rather a deterministic, order-sensitive packing that respects the input sequence.

Key concepts to master:

Conflict Detection: Two calls conflict if they share a resource and at least one is a write.
Wave Construction: A wave is a maximal set of non-conflicting, dependency-satisfied calls processed in input order.
Progress Tracking: We must track which calls have been "completed" (assigned to a previous wave) to satisfy depends_on constraints.

2. Algorithm Approach

The solution follows a greedy iterative simulation approach. Since the scheduler is order-sensitive and greedy, we cannot pre-compute all waves using standard topological sort algorithms like Kahn's algorithm directly, because the "conflict" constraint is dynamic based on what has already been packed into the current wave.

The high-level strategy is:

Maintain a set of completed_ids (initially empty).
Maintain a list of unscheduled_ids (initially all call IDs).
Loop until unscheduled_ids is empty or no progress is made: a. Initialize an empty current_wave list and a conflict_tracker (e.g., a dictionary mapping resources to their modes in the current wave). b. Iterate through unscheduled_ids in their original relative order. c. For each call, check two conditions: i. Are all its dependencies in completed_ids? ii. Does it conflict with any call already in current_wave? d. If both are true, add it to current_wave and update the conflict_tracker. e. If not, leave it in unscheduled_ids for the next pass. f. If current_wave is empty after checking all unscheduled calls, return [] (unschedulable). g. Otherwise, add current_wave to the result, update completed_ids, and remove these IDs from unscheduled_ids.

3. Step-by-Step Strategy

Preprocessing:

Create a lookup dictionary call_map mapping id to the call dict for O(1) access.
Initialize unscheduled as a list of all call IDs, preserving original order.
Initialize completed as an empty set.
Initialize result as an empty list.

Main Loop:

While unscheduled is not empty:
Initialize wave = [] and resource_states = {} (maps resource -> "read" or "write").
Initialize next_unscheduled = [] to hold calls that couldn't fit in this wave.
Iterate through each call_id in unscheduled:
Retrieve the call details.
Check Dependencies: Verify all IDs in call['depends_on'] are in completed. If not, append call_id to next_unscheduled and continue.
Check Conflicts:
Get res = call['resource'] and mode = call['mode'].
If res is not in resource_states, it's safe. Add to wave, set resource_states[res] = mode.
If res is in resource_states:
If mode == "read" and resource_states[res] == "read", it's safe. Add to wave.
Otherwise (write vs read, write vs write, read vs write), it conflicts. Append call_id to next_unscheduled.
Progress Check: If wave is empty, return [] (cycle or missing dependency).
Finalize Wave: Sort wave alphabetically and append to result.
Update completed with all IDs in wave.
Set unscheduled = next_unscheduled.

Return:

Return result.

4. Common Pitfalls

Order Sensitivity: The problem states the scheduler walks unscheduled calls in their original order. Do not sort unscheduled before iterating. Only sort the final wave for output.
Conflict Logic: Remember that read vs read is safe. Only write conflicts with anything else on the same resource. A common bug is treating all same-resource calls as conflicting.
Dependency Validation: Ensure you check dependencies against completed IDs, not just unscheduled IDs. A dependency might be in a previous wave, not just the current one.
Missing Dependencies: If a call depends on an ID that doesn't exist in the input calls list, it will never be in completed. This will cause it to stay in unscheduled forever, leading to an empty wave and correctly returning [].
Infinite Loops: If you don't detect the "no progress" case (empty wave), you might loop infinitely if there's a cycle. The check if not wave: return [] is critical.
Resource State Tracking: You must track the mode of the resource in the current wave. If the first call in a wave is a read, a subsequent read is fine, but a write is not. If the first is a write, no subsequent calls on that resource are allowed.

5. Time & Space Complexity

Time Complexity: $O(N^2)$ in the worst case, where $N$ is the number of calls.
In each iteration (wave), we iterate through all remaining unscheduled calls.
In the worst case (e.g., a long chain of dependencies or conflicts), we might only schedule one call per wave, leading to $N$ waves.
Each wave construction takes $O(N)$ time to check dependencies and conflicts.
Total time: $N \times O(N) = O(N^2)$ .
Dependency checks can be optimized to $O(1)$ per dependency if using sets, but the number of dependencies can be up to $N$ , so worst-case per call is $O(N)$ .
Space Complexity: $O(N)$ .
We store call_map, completed, unscheduled, and resource_states.
All these structures hold at most $N$ elements.
The output also stores $N$ IDs.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.