875. Koko Eating Bananas #

Problem #

Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won’t eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer K such that she can eat all the bananas within H hours.

Example 1:

Input: piles = [3,6,7,11], H = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], H = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], H = 6
Output: 23

Note:

• 1 <= piles.length <= 10^4
• piles.length <= H <= 10^9
• 1 <= piles[i] <= 10^9

Problem Summary #

Koko loves to eat bananas. There are N piles of bananas, and the i-th pile has piles[i] bananas. The guards have left and will come back in H hours.

Koko can decide her banana-eating speed K (unit: bananas/hour). Each hour, she will choose a pile of bananas and eat K bananas from it. If the pile has fewer than K bananas, she will eat all the bananas in that pile and then will not eat any more bananas during that hour.  

Koko likes to eat slowly, but still wants to eat all the bananas before the guards come back.

Return the minimum speed K (K is an integer) such that she can eat all the bananas within H hours.

Notes:

• 1 <= piles.length <= 10^4
• piles.length <= H <= 10^9
• 1 <= piles[i] <= 10^9

Solution Approach #

• Given an array, each element in the array represents the number of bananas in each banana🍌pile. koko eats these bananas at a speed of k bananas/hour. The guards will come back after H hours. Ask what the minimum value of k is so that all the bananas can be eaten before the guards return. When the number of bananas is less than k, she can only finish those bananas during that hour and cannot eat bananas from other piles.
• This problem can be solved with binary search. Search within the range [0 , max(piles)], and the binary search process follows the standard approach. When determining how to divide the left and right boundaries, pay attention to the constraints given in the problem. When the number of bananas is less than k, no other bananas can be eaten during that hour.

Code #

package leetcode

import "math"

func minEatingSpeed(piles []int, H int) int {
	low, high := 1, maxInArr(piles)
	for low < high {
		mid := low + (high-low)>>1
		if !isPossible(piles, mid, H) {
			low = mid + 1
		} else {
			high = mid
		}
	}
	return low
}

func isPossible(piles []int, h, H int) bool {
	res := 0
	for _, p := range piles {
		res += int(math.Ceil(float64(p) / float64(h)))
	}
	return res <= H
}

func maxInArr(xs []int) int {
	res := 0
	for _, x := range xs {
		if res < x {
			res = x
		}
	}
	return res
}