875. Koko Eating Bananas (Medium)

https://leetcode.com/problems/koko-eating-bananas/

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

Solutions

class Solution {

    // You can not adopt brute force approach because the size of files is really
    // large and the excution will exceeds the time limit.

    // Employ binary search from 1 to size of largest pile

    public int minEatingSpeed(int[] piles, int H) {
        // if size of banana piles is larger than hours, it can not eat up all the bananas
        int pileSize = piles.length;

        Arrays.sort(piles);

        int maxSpeed = piles[pileSize - 1];

        // if size of banana piles is as many as hours, the pile of maximum size
        // will be the min speed.

        if (piles.length == H) {
            return maxSpeed;
        }

        int least = 1;
        int most = maxSpeed;

        // Work out the threshold speed that happens to finish all the bananas and
        // even a little slower will not do.

        // binary search is important, refine this solution.
        // #TODO
        while (most - least > 1) {
            int mid = (least + most) / 2;
            if (timer(piles, mid, H)) {
                most = mid;
            } else {
                least = mid;
            }
        }

        // the answer could be left or right, check out if the left is the desired one.
        if (timer(piles, least, H)) {
            return least;
        }

        return most;
    }

    public boolean timer(int[] piles, int speed, int H) {
        int time = 0;

        for (int i = 0; i < piles.length; i++) {
            time += (piles[i] + speed - 1) / speed;
        }

        return time <= H;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""