Show problems as
Classic problem #2742HardArrayDynamic Programming

Painting the Walls

Real-world version: Restoring The Panel Gallery
Tracked in this browser only
Read Painting the Walls on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A gallery has n panels waiting to be restored and a shortlist of exactly n paid restorers, both numbered 0 through n - 1. Restorer i needs hours[i] whole hours to bring one panel back and charges fee[i] for the job. A restorer may be hired for at most one panel, and you may hire as few or as many of them as you like.

One volunteer is also available. The volunteer restores a panel in exactly one hour and charges nothing.

The work runs in whole hours, one after another. The paid restorers you hire work in sequence, in whatever order you choose, each occupying the workshop for their own number of hours. The volunteer may work during an hour when a paid restorer is at work in the workshop, restoring one panel in that hour, and may not work during any other hour.

Every panel has to be restored by exactly one worker, paid or volunteer. Return the smallest total fee that gets all n panels restored.

Examples

Example 1

Input
fee = [3, 2, 2, 2], hours = [8, 1, 1, 1]
Output
3

Hire restorer 0 alone for 3. It restores one panel and occupies the workshop for 8 hours, and the volunteer restores the other three panels in three of those hours.

Example 2

Input
fee = [1, 100], hours = [1, 100]
Output
1

Hire restorer 1 for 100. It restores one panel and holds the workshop for 100 hours, and the volunteer restores the remaining panel in the first of them.

Example 3

Input
fee = [7], hours = [1]
Output
7

There is one panel and the volunteer cannot work unless a paid restorer is in the workshop, so restorer 0 has to be hired for 7.

Constraints

  • 1 <= fee.length <= 500
  • hours.length == fee.length
  • 1 <= fee[i] <= 10^6
  • 1 <= hours[i] <= 500

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def least_restoration_fee(fee: list[int], hours: list[int]) -> int:
Java
public int leastRestorationFee(int[] fee, int[] hours)

More on the same topics