Minion Chef and Bananas - Binary Search on Answer (C++)

general
1

Problem: Find minimum speed k to eat all bananas within h hours.

Approach: Binary Search on the answer (speed k).

Code (C++):
int minEatingSpeed(vector& piles, int h) {
int lo = 1, hi = *max_element(piles.begin(), piles.end());
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
long long hours = 0;
for (int p : piles)
hours += (p + mid - 1) / mid;
if (hours <= h)
hi = mid;
else
lo = mid + 1;
}
return lo;
}

Example:
piles = [3,6,7,11], h = 8
Answer = 4 (minimum speed)

Key Idea: Binary search on answer, not on array!

Time: O(n log m) | Space: O(1)

1 Like