Paid Free Server Cost
MediumDynamic Programming · Snowflake
There are n tasks to run, and every task must run exactly once on one of two servers:
- The paid server runs task
ifortime[i]units at a cost ofcost[i]. It runs its tasks one after another. - The free server runs any task in exactly
1unit at no cost, but it may only work while the paid server is busy. So during the paid server's total busy timeT, the free server can finish at mostTtasks.
Choose which tasks go on the paid server. Return the minimum total cost to finish all n tasks.
Example 1
- Input:
- cost = [1, 1, 3, 4], time = [3, 1, 2, 3]
- Output:
- 1
- Explanation
- Putting task 0 on the paid server costs 1 and keeps it busy for 3 units, enough for the free server to finish the other 3 tasks.
Example 2
- Input:
- cost = [2, 3, 4], time = [1, 1, 1]
- Output:
- 5
- Explanation
- Each paid task here frees only 1 slot, so one paid task covers just 2 tasks. Two paid tasks cover all 3, and the cheapest two cost
2 + 3 = 5.
Example 3
- Input:
- cost = [8, 2, 5, 1, 6], time = [1, 1, 2, 1, 1]
- Output:
- 6
- Explanation
- Paying for tasks 1 and 3 (cost 3) covers only 4 tasks. Tasks 2 and 3 cost 6 and cover
(2 + 1) + (1 + 1) = 5tasks, which is the cheapest way to cover all five.
Constraints
- 1 ≤
n==cost.length==time.length≤ 500 - 1 ≤
cost[i]≤ 106 - 1 ≤
time[i]≤ 500