Paint Every Wall at Minimum Cost with Two Painters
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Paint Every Wall at Minimum Cost with Two Painters
You are given 0-indexed integer arrays `cost` and `time`, each containing one entry for each of `n` different walls. Two painters are available:
- The paid painter takes `time[i]` time units to paint wall `i` and charges `cost[i]`.
- The free painter can paint any wall in one time unit for no money, but can work only while the paid painter is occupied.
Choose which walls each painter paints and return the minimum total amount of money needed to paint all `n` walls.
### Examples
**Example 1**
```text
Input: cost = [5,2,4], time = [2,1,1]
Output: 5
```
Pay for wall `0`, which takes two time units. During that time the free painter completes walls `1` and `2`. Paying only for wall `1` or only for wall `2` leaves insufficient time to finish the other two walls; paying for both costs `6`. Thus `5` is optimal.
**Example 2**
```text
Input: cost = [4,1,7,3], time = [1,1,2,1]
Output: 4
```
Pay for walls `1` and `3`, costing `1 + 3 = 4`. Their two time units of work let the free painter finish walls `0` and `2`. A cost below `4` could pay only for wall `1` or only for wall `3`, neither of which provides enough time to finish all four walls.
### Constraints
- `1 <= cost.length <= 500`.
- `cost.length == time.length`.
- `1 <= cost[i] <= 10^6`.
- `1 <= time[i] <= 500`.
### Clarifying Questions
- Is `time[i]` also the free painter's time for wall `i`? No; the free painter always needs one time unit per wall.
- Can the free painter keep working while the paid painter is idle? No; the paid painter must be occupied throughout the free painter's work.
- Must the paid painter paint every wall? No; assign the other walls to the free painter while paid work is underway.
- Are the arrays in wall order that must be followed? No painting order is specified; the indices identify walls and their individual paid costs and times.
### C++ Interface
```cpp
class Solution {
public:
int paintWalls(vector<int>& cost, vector<int>& time) {
}
};
```
### Reasoning Checkpoints
- Relate the amount of paid work to the amount of free work that can be completed.
- Justify that a proposed assignment can be scheduled with both painters' restrictions.
- Ensure each wall can be selected for paid work at most once.
```hint Paid time and free work
For a fixed set of walls assigned to the paid painter, how many other walls can the free painter finish during that paid work?
```
Overview: Choose paid and free painting work to finish every wall at minimum cost, with the free painter available only while the paid painter is occupied.
