Search on the answer

Why it matters

Schedulers often need the cheapest capacity that still meets a deadline. Testing candidate capacities one by one is expensive when the upper bound is large, yet returning any feasible value may overprovision the system. For piles [3, 6, 7, 11] and h = 8, return the smallest integer rate, 4, without checking each candidate in sequence.

Koko eats bananas at integer speed k piles/hour, one pile at a time, rounding up. Return the minimum k so she finishes all piles in h hours.

Input

piles = [3, 6, 7, 11], h = 8

Output

4

For [3, 6, 7, 11], rate 6 takes 6 hours and fits h = 8, while rate 3 takes 10 and fails. Because faster rates cannot turn success into failure, halve the candidate rates instead of brute testing 1, 2, 3, 4 in sequence.

A pile p takes ceil(p / k) hours because Koko switches piles only on an hour boundary. At k = 6, [3, 6, 7, 11] takes [1, 1, 2, 2], or 6 hours, so 6 works. At k = 3 it takes [1, 2, 3, 4], or 10 hours, so 3 fails.

Search rates 1 through 11. A working rate keeps itself as a candidate and lowers hi; a failing rate raises lo past itself. The checks narrow from 6 to 3, then 5, then 4. lo and hi meet at 4, the first rate whose total is at most 8.