875.koko-eating-bananas.cpp

/*
 * @lc app=leetcode id=875 lang=cpp
 *
 * [875] Koko Eating Bananas
 *
 * https://leetcode.com/problems/koko-eating-bananas/description/
 *
 * algorithms
 * Medium (46.65%)
 * Total Accepted:    15.2K
 * Total Submissions: 32.5K
 * Testcase Example:  '[3,6,7,11]\n8'
 *
 * 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
 * 
 * 
 * 
 * 
 * 
 */
class Solution {
public:
    int minHrs(int k, vector<int>& piles){
        long count = 0;
        for(auto e: piles){
            count += ceil((float)e/k);
            if(count>=INT_MAX)
                return INT_MAX;
        }
        return count;
    }
    int minEatingSpeed(vector<int>& piles, int H) {
        int minn = INT_MAX, maxx = INT_MIN;
        for(auto e: piles)
            minn = min(minn, e), maxx = max(maxx, e);
        
        // minn = max(0, minn);
        int pos = maxx;

        
        for(int k = maxx-1; k>=1; k/=2)
            while(pos-k>0 && minHrs(pos-k, piles)<=H)
                pos -= k;
        return pos;
    }
};