Why it works
- The faster you eat, the fewer hours it takes. So over speeds 1, 2, 3, … the checks "in time?" go no, …, no, yes, …, yes, and the answer is the first yes.
- A pile takes ceil(pile / speed) hours: at most speed bananas an hour, and never two piles in one hour. So a small pile still costs a whole hour, as the pile of 2 does at speed 6.
- If mid is in time, it may be the answer, so hi = mid keeps it. If not, every slower speed is late too: lo = mid + 1.
Complexity
Time O(n log m), where n is the number of piles and m the biggest pile: about log m speeds are tried, and each check walks over all piles. Memory O(1).
nextNow solve it yourself, no hints.
Solve on LeetCode ↗