Daily Algorithm - Koko Eating Bananas

Description

Koko loves to eat bananas. There are n piles of bananas, the ith 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 will not eat any more bananas during this hour.

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

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

Constraints:

• 1 <= piles.length <= 104
• piles.length <= h <= 109
• 1 <= piles[i] <= 109

Solution

• k는 piles의 원소들을 모두 소진할 수 있는 가장 작은 수이므로 k의 범위는 1 ≤ k ≤ piles.max() 가 된다. 이 범위 내에서 piles의 원소들을 k로 나눠서 나온 시간의 합(hour)이 h 보다 작거나 같아야 한다.
• 위 조건을 만족하는 k 중 가장 작은 수를 구해야하므로 minK 값을 두고 구한 시간 합(hour)이 h보다 작으면 minK를 최소값으로 갱신하는 과정을 거쳐 최종적으로 minK 값을 반환하면 된다.
• k의 범위 내에서 값을 구하는 과정에 이진 탐색을 활용할 수 있다.
• k 범위 내에서 piles의 원소들을 k로 나눠서 값을 계속 비교해야 하는데, 이진 탐색을 사용하지 않으면 시간 복잡도는 O(piles.max() * piles.size) 가 된다.
• 이 과정에 이진 탐색을 적용하면 O(log(piles.max()) * piles.size)가 되므로 더 효율적인 탐색이 가능하다.

class Solution {
    fun minEatingSpeed(piles: IntArray, h: Int): Int {
        var l = 1
        var r = piles.max()!!
        var minK = r

        while (l <= r) {
            val k = (l + r) / 2
            val hour = piles.fold(0) { total, num ->
                total + Math.ceil(num.toDouble() / k).toInt()
            }
            if (hour in 1 .. h) {
                r = k - 1
                minK = Math.min(minK, k)
            } else {
                l = k + 1
            }
        }
        return minK
    }
}