Slowest Eating Speed Within a Deadline

medium binary search answer search

Problem

Given pile sizes and an hour budget H, find the smallest integer eating rate r such that the eater finishes all piles in H hours, where finishing a pile of size p at rate r takes ⌈p/r⌉ hours. Binary-search on the answer space [1, max(piles)]; the feasibility check is monotone.

Inputpiles = [3, 6, 7, 11], H = 8

Output4

Rate 4 takes ⌈3/4⌉+⌈6/4⌉+⌈7/4⌉+⌈11/4⌉ = 1+2+2+3 = 8 hours.

piles (positive integers)

H (hours)

def min_eating_speed(piles, H):
    def can(r): return sum((p + r - 1) // r for p in piles) <= H
    l, r = 1, max(piles)
    while l < r:
        m = (l + r) // 2
        if can(m): r = m
        else: l = m + 1
    return l

function minEatingSpeed(piles, H) {
  const can = r => piles.reduce((s, p) => s + Math.ceil(p / r), 0) <= H;
  let l = 1, r = Math.max(...piles);
  while (l < r) {
    const m = (l + r) >> 1;
    if (can(m)) r = m; else l = m + 1;
  }
  return l;
}

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int max = 0; for (int p : piles) if (p > max) max = p;
        int l = 1, r = max;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (canEat(piles, m, H)) r = m; else l = m + 1;
        }
        return l;
    }
    private boolean canEat(int[] piles, int rate, int H) {
        long s = 0; for (int p : piles) s += (p + rate - 1) / rate;
        return s <= H;
    }
}

bool canEat(vector<int>& piles, int rate, int H) {
    long long s = 0; for (int p : piles) s += (p + rate - 1) / rate;
    return s <= H;
}
int minEatingSpeed(vector<int>& piles, int H) {
    int l = 1, r = *max_element(piles.begin(), piles.end());
    while (l < r) {
        int m = (l + r) / 2;
        if (canEat(piles, m, H)) r = m; else l = m + 1;
    }
    return l;
}

Time: O(n log max) Space: O(1)