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 = 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)