Fewest Jugs
sizes[i] is how many liters jug i holds. You have to carry liters liters of water, spread over as few jugs as possible. A jug may be filled up to its size or left partly empty.
Return the fewest jugs that can hold all the water together. If even all the jugs together are too small, return -1. When liters is 0 no jug is needed, so return 0.
Example 1
sizes [5,3,8]
liters 10
returns 2
No single jug holds 10 liters. The two biggest hold 8 + 5 = 13, which is enough.
Example 2
sizes [2,2,2]
liters 7
returns -1
All three jugs together hold only 6 liters.
Example 3
sizes [4,4]
liters 0
returns 0
There is no water to carry.
Constraints
0 <= len(sizes) <= 201 <= sizes[i] <= 500 <= liters <= 600
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Greedy problems
- Greedy CoinsBeginner
- Least Total Waiting TimeBeginner
- Most Tasks in a Time BudgetBeginner
- Only the Best CountBeginner
- Shortest Walk to SeatsBeginner
- Stepping StonesBeginner
- Third One FreeBeginner
- Two Numbers From Four DigitsBeginner