Timeout Budget Split Across Sequential Steps
Problem Statement
An agent plan runs steps sequentially under one overall timeout. Assign each step a per-step timeout proportional to its expected cost, but never below a floor, and report whether the plan fits.
Background
Given a total budget and per-step expected costs costs, the naive split gives step i a share budget * costs[i] / sum(costs). To avoid starving cheap steps, each allocation is raised to at least floor seconds. Because flooring can push the sum over budget, the plan is feasible only if sum(max(share_i, floor)) <= budget. Report each allocation (rounded to 4 decimals) and feasibility.
Your Task
def split_timeout(costs, budget, floor):
Return a dict {"allocations": [...], "feasible": bool}, allocations rounded to 4 decimals.
Input Format
- costs (list of positive floats), budget (float), floor (float).
Output Format
- A dict with "allocations" (list of floats) and "feasible" (bool).
Sample
print(split_timeout([1.0, 3.0], 8.0, 0.5))
Output:
{'allocations': [2.0, 6.0], 'feasible': True}
Example:
print(split_timeout([1.0, 3.0], 8.0, 0.5))
{'allocations': [2.0, 6.0], 'feasible': True}- Calculate the total expected cost to determine proportional weights: total=1.0+3.0=4.0.
- Compute the raw proportional share for each step using the formula sharei=budget×totalcosti:
- Step 1: 8.0×4.01.0=2.0
- Step 2: 8.0×4.03.0=6.0
- Apply the minimum floor constraint by taking the maximum of the raw share and the floor value (0.5):
- Step 1: max(2.0,0.5)=2.0
- Step 2: max(6.0,0.5)=6.0
- Check feasibility by summing the final allocations and comparing to the budget: 2.0+6.0=8.0, which is ≤8.0, so the plan is feasible.
- The final output is
{'allocations': [2.0, 6.0], 'feasible': True}
Constraints:
- Share is
budget * costs[i] / sum(costs), then raised tofloor. feasibleissum(allocations) <= budget(use a small tolerance).- Round allocations to 4 decimals;
costsis non-empty with positive sum.
1. Background Knowledge
This problem models resource allocation under constraints, a core concept in systems design and AI agent planning. When an agent executes a sequence of steps (e.g., API calls, tool invocations), each step consumes time. A global timeout budget must be distributed across steps so that no single step monopolizes the entire window, yet no step is starved of the minimum time it needs to complete.
The allocation strategy here is proportional allocation with a floor constraint. Without the floor, step i would receive sharei=budget×∑costscosts[i]. This ensures that steps with higher expected costs get more time. However, if a step has a very small cost relative to others, its proportional share might be unreasonably small (e.g., 0.01 seconds), making it impossible to complete. The floor guarantees a minimum allocation: alloci=max(sharei,floor).
The critical insight is that applying the floor can violate the budget constraint. If many steps hit the floor, the sum of allocations may exceed the total budget. In that case, the plan is infeasible—the agent cannot guarantee all steps will complete within the timeout. Feasibility is thus a binary check: does ∑alloci≤budget?
2. Algorithm Approach
This is a deterministic allocation with feasibility check problem. The approach is:
- Compute the proportional share for each step based on its cost relative to total cost.
- Apply the floor constraint by taking the maximum of the share and the floor value.
- Sum all allocations and compare against the budget to determine feasibility.
- Return the rounded allocations and the feasibility flag.
No iterative adjustment or optimization is needed—the allocation rule is fixed, and feasibility is a simple comparison.
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.