#7
Binary Search on the Answer
Binary Search on AnswerPiles of bananas and h hours are given. Choose the smallest integer eating-speed such that all piles can be finished within h hours.
function minEatingSpeed(piles: number[], h: number): number {
const hoursNeeded = (speed: number): number =>
piles.reduce((sum, p) => sum + Math.ceil(p / speed), 0);
let lo = 1, hi = Math.max(...piles);
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (hoursNeeded(mid) <= h) hi = mid; // fast enough → try slower
else lo = mid + 1; // too slow → speed up
}
return lo;
}def min_eating_speed(piles, hours)
hours_needed = ->(speed) { piles.sum { |p| (p + speed - 1) / speed } }
lo = 1
hi = piles.max
while lo < hi
mid = lo + ((hi - lo) / 2)
if hours_needed.call(mid) <= hours
hi = mid # fast enough -> try slower
else
lo = mid + 1 # too slow -> speed up
end
end
lo
end