875. Koko Eating Bananas
Intuition
Koko wants to finish eating all the bananas within h
hours. She eats from one pile per hour, and the speed k
(bananas/hour) is the same for all hours. The faster she eats, the fewer hours she'll take.
The problem is to find the minimum possible eating speed k
such that total time ≤ h
. Since the relationship between speed and hours is monotonic (higher speed → fewer hours), we can apply binary search on k
.
Complexity
Space Complexity
Time Complexity
Code
// Helper function to calculate how many hours it takes to eat all bananas at speed 'eatingSpeed'
long hoursToFinish(int[] bananaPiles, long eatingSpeed) {
long totalHours = 0;
for (int pile : bananaPiles) {
// Each pile takes ceil(pile / eatingSpeed) hours to eat
totalHours += pile / eatingSpeed;
if (pile % eatingSpeed != 0) totalHours++;
}
return totalHours;
}
public int minEatingSpeed(int[] bananaPiles, int allowedHours) {
long minSpeed = 1;
long maxSpeed = 1;
long optimalSpeed = 0;
// Find the maximum pile size to set upper limit for binary search
for (int pile : bananaPiles) {
maxSpeed = Math.max(maxSpeed, pile);
}
// Binary search on eating speed
while (minSpeed <= maxSpeed) {
long midSpeed = minSpeed + (maxSpeed - minSpeed) / 2;
long requiredHours = hoursToFinish(bananaPiles, midSpeed);
if (requiredHours <= allowedHours) {
optimalSpeed = midSpeed; // Try to find a slower (minimal) valid speed
maxSpeed = midSpeed - 1;
} else {
minSpeed = midSpeed + 1; // Too slow, increase speed
}
}
return (int) optimalSpeed;
}
Last updated