536. Koko Eating Bananas
Koko has n piles of bananas in front of her, where piles[i] is the size of the i-th pile, and exactly h hours before the guards return. She picks an eating speed k (bananas per hour) and sticks with it: each hour she chooses one pile and eats k bananas from it — or the whole pile if fewer than k remain, in which case she eats nothing else that hour. A pile can take several hours; an hour never covers two piles.
Return the smallest integer speed k that lets her finish every pile within h hours. You are guaranteed h >= n, so a valid speed always exists.
Example 1:
Input: piles = [3, 6, 7, 11], h = 8
Output: 4
Explanation: At speed 4 the piles take ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8 hours — exactly the budget. At speed 3 they take 10 hours, too many, so 4 is the minimum.
Example 2:
Input: piles = [30, 11, 23, 4, 20], h = 5
Output: 30
Explanation: Five piles and five hours means every pile must vanish in a single hour, so k has to reach the largest pile: 30.
Example 3:
Input: piles = [30, 11, 23, 4, 20], h = 6
Output: 23
Explanation: With one spare hour, the pile of 30 may be split across two hours: at k = 23 the hours are 2 + 1 + 1 + 1 + 1 = 6. Any slower and the total exceeds 6.
Constraints:
- 1 ≤ piles.length ≤ 10⁴
- piles.length ≤ h ≤ 10⁹
- 1 ≤ piles[i] ≤ 10⁹
Hints:
For a fixed speed k, the time needed is easy: pile p takes ceil(p / k) hours, and the total is the sum over all piles. So you don't need to *construct* the answer — you only need to *test* candidate speeds.
Feasibility is monotone: if speed k finishes in time, every speed above k does too. A yes/no property that flips exactly once over a sorted range of candidates is the signature of binary search on the answer.
Search k between 1 and max(piles). While lo < hi: test mid = (lo + hi) / 2; if it finishes within h keep it (hi = mid), otherwise discard it (lo = mid + 1). Watch for 64-bit overflow when summing the hours.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: piles = [3, 6, 7, 11], h = 8
Expected output: 4