Module 12 · Binary Search and Monotone Answer Spaces

119. Minimum Eating Speed

Interview · Download this solution · All solutions and shared helpers

Problem

Given positive integer pile sizes and h available hours, choose the smallest positive integer speed. In one hour you process up to speed units from one pile; unused capacity in that hour cannot transfer to another pile. Return None if h is smaller than the number of nonempty piles, and zero for no piles.

Examples

Example 1

minimum_eating_speed([3,6,7,11], 8)
=> 4

Speed four is the first to fit eight hours.

Example 2

minimum_eating_speed([2,3], 1)
=> None

Two piles require at least two separate hours.

Example 3

minimum_eating_speed([], 0)
=> 0

No work needs no processing speed.

Reveal the worked solution and reasoning

Why this mechanism works

At speed s, each pile needs ceil(pile/s) hours. Increasing speed cannot increase total hours, so feasibility is false then true. With at least one hour per pile, speed max(piles) is feasible, giving a finite upper bound for a first-true search.

State and boundaries

left and right bound the first feasible speed. hours is a complete feasibility calculation for the current midpoint.

Protocol

Handle no piles or too few hours.
Search speeds in [1,max(piles)+1).
Compute total ceiling-divided hours.
On feasibility move right to mid.
Otherwise move left to mid+1.
Return the first feasible speed.

Visualization

piles 3,6,7,11; h=8
speed 3 -> 1+2+3+4=10 hours
speed 4 -> 1+2+2+3=8 hours
first feasible speed is 4

Python implementation

def minimum_eating_speed(piles, h):
    if not piles:
        return 0
    if h < len(piles):
        return None
    left, right = 1, max(piles) + 1
    while left < right:
        mid = (left + right) // 2
        hours = sum((pile + mid - 1) // mid for pile in piles)
        if hours <= h:
            right = mid
        else:
            left = mid + 1
    return left

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

minimum_eating_speed([3,6,7,11], 8)

L2 minimum_eating_speed: if not piles:
piles=[3, 6, 7, 11]; h=8

L6 minimum_eating_speed: left, right = 1, max(piles) + 1
piles=[3, 6, 7, 11]; h=8; left=1; right=12

L8 minimum_eating_speed: mid = (left + right) // 2
piles=[3, 6, 7, 11]; h=8; left=1; right=12; mid=6

L9 <genexpr>: hours = sum((pile + mid - 1) // mid for pile in piles)
.0=list_iterator; pile=3; mid=6

L9 <genexpr>: hours = sum((pile + mid - 1) // mid for pile in piles)
.0=list_iterator; pile=6; mid=6

L9 <genexpr>: hours = sum((pile + mid - 1) // mid for pile in piles)
.0=list_iterator; pile=7; mid=6

L9 <genexpr>: hours = sum((pile + mid - 1) // mid for pile in piles)
.0=list_iterator; pile=11; mid=6

L9 <genexpr>: hours = sum((pile + mid - 1) // mid for pile in piles)
.0=list_iterator; pile=11; mid=6

... 21 intermediate state changes omitted ...

L9 <genexpr>: hours = sum((pile + mid - 1) // mid for pile in piles)
.0=list_iterator; pile=7; mid=4

L9 <genexpr>: hours = sum((pile + mid - 1) // mid for pile in piles)
.0=list_iterator; pile=11; mid=4

L9 <genexpr>: hours = sum((pile + mid - 1) // mid for pile in piles)
.0=list_iterator; pile=11; mid=4

L11 minimum_eating_speed: right = mid
piles=[3, 6, 7, 11]; h=8; left=4; right=4; mid=4; hours=8

Result: 4. Speed four is the first to fit eight hours.

minimum_eating_speed([2,3], 1)

L2 minimum_eating_speed: if not piles:
piles=[2, 3]; h=1

Result: None. Two piles require at least two separate hours.

Why the solution is correct

The per-pile ceiling formula follows from the no-cross-pile hour rule. Its sum is nonincreasing with speed. Binary search therefore finds the first feasible integer, and the established feasible upper bound guarantees an answer when the preliminary impossibility check passes.

Time and space

O(p log M) time and O(1) auxiliary space for p piles and maximum size M.

Common mistakes

Using floor division underestimates hours for partial final work. Searching array indices instead of speed values models the wrong answer space.

Reasoning card

State: left and right bound the first feasible speed. hours is a complete feasibility calculation for the current midpoint.

Invariant: Speeds below the answer fail; at or above it succeed.

Decision to rehearse: Binary-search a monotone feasibility predicate.

Finish: Return the first feasible speed

Transfer exercise

Stop the feasibility scan once accumulated hours exceeds h; explain why this optimization cannot change its Boolean answer.