Koko Eating Bananas

Find the slowest eating speed that still finishes every pile within h hours, by binary searching on the speed itself.

The idea

At speed k a pile of p bananas takes ceil(p / k) hours, because Koko eats from only one pile per hour and the rest of that hour is wasted. Total hours only go down as k goes up, so the speeds split into "too slow" followed by "fast enough". Binary search finds the first fast-enough speed between 1 and the biggest pile (eating faster than the biggest pile never helps).

Code

public static int MinEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = piles.Max();
    while (lo < hi) {
        int k = lo + (hi - lo) / 2;
        long hours = 0;
        foreach (int p in piles) hours += (p + k - 1) / k;
        if (hours <= h) hi = k;
        else lo = k + 1;
    }
    return lo;
}

Tips

• (p + k - 1) / k is ceil(p / k) using integer maths only, with no doubles.
• Fast enough: hi = k, because k might be the answer. Too slow: lo = k + 1, because k is ruled out.
• The same "binary search on the answer" pattern solves Capacity to Ship Packages, Split Array Largest Sum and Minimum Days to Make Bouquets.

In the .NET library

piles.Max() needs using System.Linq. Keep hours in a long: with big piles and k = 1 the sum can overflow an int.