Given a number of people N and an array of integers, each one representing the amount of people a type of umbrella can handle, output the minimum number of umbrellas needed to handle N people.
No umbrella could have left spaces. Which means if a umbrella can handle 2 people, there should be 2 people under it.
If there's no solution, return -1
.
solve(3, [1, 2])
means that we have 3 people and two kinds of umbrellas, one that hanled one person and one that handles 2.
We can give one two-sized umbrella to 2 of them and the other to the last person. Therefore the solution is 2
(umbrellas).
You could give 3 one-sized umbrellas, but we want the minimum number.
solve(10, [3, 1])
. You can give 3 three-sized umbrellas and 1 one-sized. This means the solution is 4
.
solve(3, [2])
. There's no solution since one umbrella would have empty space. Return -1
.
This question is exactly same as "coin change problem" where we have infinite number of coins of each type and we have to find minimum number of coins to make change. One can practice here.
This is my solution