Koko Eating Bananas

Medium

The problem

Koko has piles of bananas and h hours before the guards return. Each hour she picks one pile and eats up to k bananas from it; if the pile has fewer than k, she finishes it and does nothing else that hour. Return the smallest whole number k that lets her eat all the bananas within h hours.

Example 1
Input: piles = [5, 10, 3], h = 4
Output: 5
At k = 5 the piles take 1 + 2 + 1 = 4 hours. At k = 4 they would take 2 + 3 + 1 = 6 hours, which is too slow.
Example 2
Input: piles = [30], h = 30
Output: 1
At 1 banana per hour the single pile takes exactly 30 hours.

Limits

1 ≤ piles.length ≤ 10,000
piles.length ≤ h ≤ 1,000,000,000
1 ≤ piles[i] ≤ 1,000,000,000

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

You are not searching the piles — you are searching for the speed. If speed k works, does k+1 work too?

The idea

Binary search k in [1, max pile]. For a candidate k, hours = sum of ceil(pile/k). Find the smallest k with hours ≤ h.

Target: O(n log max) time

Go function shape

func minEatingSpeed(piles []int, h int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// MinEatingSpeed: smallest speed k so every pile is eaten within h hours.
// Search the ANSWER space [1, max(piles)]: "can finish at speed k" is false..false,true..true.
func MinEatingSpeed(piles []int, h int) int {
	maxPile := 0
	for _, p := range piles {
		maxPile = max(maxPile, p)
	}
	// candidate speed for index i is i+1
	i := firstTrue(maxPile, func(i int) bool {
		k, hours := i+1, 0
		for _, p := range piles {
			hours += (p + k - 1) / k // ceil(p / k)
		}
		return hours <= h
	})
	return i + 1
}

Read the lesson: Binary Search