875. Koko Eating Bananas

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:

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for (int p : piles){
            right = Math.max(right, p);
        }

        int result = right;

        while(left <= right){
            int mid = left + (right - left) / 2;

            if (canFinish(piles, mid, h)){
                result = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }

        return result;
    }

    private boolean canFinish(int[] piles, int k, int h){
        long time = 0;
        for (int p : piles){
            time = time + (int) Math.ceil((double) p / k);
            if (time > h){
                return false;
            }
        }

        return true;
    }
}

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 1;

        for (int i = 0; i < piles.length; i++){
            right = Math.max(piles[i], right);
        }

        int result = right;

        while (left <= right){
            int mid = left + (right - left)/2;
            int hourSpent = 0;


            for (int pile : piles){
                hourSpent +=  Math.ceil( (double) pile / mid) ;

                // hourSpent = (int)(Math.ceil ((double) pile/ mid) + hourSpent);
              // 先加 再类型转换, 不然数量越来越大, 精度的差值会导致有些case不通过
            }

            //Careful here, when we want to get float number of integer devision and round it up
                //We need to cast it to float / double first
                //But for this problem , Float won't work becasue it can have maximum 6-7 digits 
                //but the input is maximum 10^9 , so we need to use double here which can have maximum 15 digits

            if (hourSpent <= h){
                result = Math.min(result, mid);
                right = mid-1;
            }else{
                left = mid + 1;
            }
        }

        return result;
    }
}
// TC: O(nlogn)
// SC: O(1)

long 是 整数类型（整型），没有小数部分。
-9,223,372,036,854,775,808
到
 9,223,372,036,854,775,807
double 是 浮点数类型（小数）。

在 Koko 吃香蕉题里为什么用 long？
long time = 0;
time += (p + k - 1) / k;
因为：

time 可能很大（n 最多 10^4，每堆最多 10^9）

用 int 可能溢出

用 long 是为了防溢出

不能用 double，会有精度问题

Ceiling–Floor Conversion Formula

When $a$ is a non-negative integer and $b$ is a positive integer, the following identity always holds: $$ \left\lceil \frac{a}{b} \right\rceil = \left\lfloor \frac{a + b - 1}{b} \right\rfloor $$ This is called the “ceiling–floor conversion formula.”

Proof

We consider two cases:

Case 1: $a \bmod b = 0$

Then the left side of the identity equals: $$ \frac{a}{b} $$ The right side becomes: $$ \left\lfloor \frac{a + b - 1}{b} \right\rfloor = \left\lfloor \frac{a}{b} + \frac{b - 1}{b} \right\rfloor = \frac{a}{b} + \left\lfloor \frac{b - 1}{b} \right\rfloor = \frac{a}{b} $$ Thus, the identity holds.

Case 2: $a \bmod b > 0$

Then the left side equals: $$ \left\lfloor \frac{a}{b} \right\rfloor + 1 $$ Since: $$ \left\lfloor \frac{a}{b} \right\rfloor = \left\lfloor \frac{a - 1}{b} \right\rfloor $$ the right side becomes: $$ \left\lfloor \frac{a - 1 + b}{b} \right\rfloor = \left\lfloor \frac{a - 1}{b} + \frac{b}{b} \right\rfloor = \left\lfloor \frac{a}{b} \right\rfloor + 1 $$ Thus, the identity also holds.

Question & Answer

Question: Can we use the library function ceil to compute the ceiling directly?

Answer: Doing so converts integers into floating-point numbers, which may introduce rounding errors and cause incorrect results.

For example, the correct value of: $$ \frac{a}{b} = 2 $$ But due to floating-point precision, the computed value might be:

2.000000001

In this case:

The correct ceiling result is 2
But applying ceil to 2.000000001 would incorrectly give 3

Therefore, using integer arithmetic with the formula: $$ \left\lfloor \frac{a + b - 1}{b} \right\rfloor $$ is safer and more reliable.

875. Koko Eating Bananas

Ceiling–Floor Conversion Formula

Proof

Case 1: \(a \bmod b = 0\)

Case 2: \(a \bmod b > 0\)

Question & Answer