Cheapest Way to Paint Every Wall With a Paid and a Free Painter
A paid painter charges a cost and takes a set time per wall; a free painter is free but takes one unit of time per wall and may work only while the paid painter is busy. Paint all walls at minimum total cost.
Problem
Given arrays cost and time of length n where painting wall i with the paid painter costs cost[i] and takes time[i] units, and a free painter paints any wall in 1 unit but can only be used while the paid painter is occupied, return the minimum total cost to paint all n walls.
Input
Two arrays cost and time of equal length n.
Output
An integer: the minimum total cost.
Constraints
- 1 <= n <= 500
- 1 <= cost[i] <= 10^6, 1 <= time[i] <= 500
- The free painter needs the paid painter to be busy.
Examples
Example 1
Input
cost = [1,2,3,2], time = [1,2,3,2]
Output
3
Pay for walls 0 and 1 (cost 3, time 3); the free painter covers the other two.
Example 2
Input
cost = [2,3,4,2], time = [1,1,1,1]
Output
4
Pay for walls 0 and 3 (cost 4); the free painter handles two walls in the 2 time units.