Pipeline Throughput Budget
MediumOptimization · Citadel
A data pipeline runs as a sequence of stages, and every stage must be provisioned. stages[i] lists the options for stage i; each option is [throughput, cost]. You must choose exactly one option for every stage, and the total cost of the chosen options must be at most budget.
The pipeline's throughput is limited by its slowest stage, so it equals the minimum throughput among the chosen options.
Return the maximum pipeline throughput you can achieve within the budget. If even the cheapest possible choice for every stage costs more than budget, return 0.
Example 1
- Input:
- stages = [[[12, 4], [30, 9], [18, 6]], [[25, 7], [10, 2]], [[15, 3], [40, 12]]], budget = 20
- Output:
- 15
- Explanation
- To reach 15, take 18 (cost 6), 25 (cost 7) and 15 (cost 3), for a total of 16. Reaching 18 would force the third stage to its 40 option, for a total of 6 + 7 + 12 = 25, which is over the budget of 20.
Example 2
- Input:
- stages = [[[10, 5], [20, 9]], [[8, 4], [15, 10]]], budget = 13
- Output:
- 8
- Explanation
- The 15 option of the second stage costs 10, and with even the cheapest first stage that totals 15. So the second stage must use its 8 option, which caps the pipeline at 8 no matter what the first stage gets.
Example 3
- Input:
- stages = [[[10, 5]], [[8, 4]]], budget = 8
- Output:
- 0
- Explanation
- The only possible plan costs 9, which is over the budget, so the answer is 0.
Constraints
1 <= stages.length <= 10001 <= stages[i].length, and the total number of options across all stages is at most10^50 <= throughput <= 10^9and0 <= cost <= 10^90 <= budget <= 10^14