Koko Eating Bananas

LeetCode 875 · View on LeetCode

Binary search on the answer. Search space is [1, max(piles)]. For each speed, check if Koko can finish in h hours. Find the minimum speed that works.

package main

import "fmt"

func minEatingSpeed(piles []int, h int) int {
	lo, hi := 1, 0
	for _, p := range piles {
		if p > hi {
			hi = p
		}
	}

	for lo < hi {
		mid := lo + (hi-lo)/2
		hours := 0
		for _, p := range piles {
			hours += (p + mid - 1) / mid // ceil division
		}
		if hours <= h {
			hi = mid // try slower
		} else {
			lo = mid + 1 // need faster
		}
	}
	return lo
}

func main() {
	fmt.Println(minEatingSpeed([]int{3, 6, 7, 11}, 8))    // 4
	fmt.Println(minEatingSpeed([]int{30, 11, 23, 4, 20}, 5)) // 30
	fmt.Println(minEatingSpeed([]int{30, 11, 23, 4, 20}, 6)) // 23
}