A nightly ETL has to drain every shard file before the 6am cutover. Each file takes ceil(bytes / rate) hours at a chosen throughput, and the job reads one file at a time. Ops asked for the smallest rate that still finishes in h hours. The first version started at rate 1 and incremented. A handful of small shards returned instantly. After the warehouse dump, the largest file was in the billions of bytes and the search was still incrementing when the window closed.

Koko asks for the slowest speed that still finishes by hour h. An array already gives each pile size. Sorting those piles does not help — you still visit every pile to total the hours. What is sorted is the yes/no predicate on k.

This is an interview writeup, not a procedure lecture. The binary search post owns the invariant and mid overflow. The membership writeup searches a sorted array for a value. Here the “array” is the integer range 1 .. max(pile), and the comparison is “does this speed finish by hour h?”

The problem

Given an int[] piles of pile sizes and an int h (hours you may spend), return the minimum integer eating speed k such that every pile is finished in at most h hours. You eat from one pile per hour. At speed k, a pile of size p takes ceil(p / k) hours, and leftover hours in that hour are idle — you do not start the next pile mid-hour. Typical interviews want better than a linear scan of every speed.

piles = [4, 8, 9, 13],          h = 8  →  5
piles = [40, 12, 25, 6, 18],    h = 5  →  40
piles = [40, 12, 25, 6, 18],    h = 6  →  25

Note: h is at least piles.length: one hour per pile is the floor. If they hand you a smaller h, say the input is illegal. You never need k larger than the biggest pile — that pile already finishes in one hour.

Try every speed is the honest brute force

From k = 1 to max(pile), total the hours and keep the first speed that fits. Correct. Linear in the max pile, times a pass over the piles each try.

int minEatingSpeedScan(int[] piles, int h) {
    int max = 0;
    for (int p : piles) {
        max = Math.max(max, p);
    }
    for (int k = 1; k <= max; k++) {
        if (finishes(piles, h, k)) {
            return k;
        }
    }
    return max;
}

At a max pile of 13 this is a rounding error. At a max in the hundreds of millions you paid a walk of the speed axis for a question a monotonic check answers in a handful of probes: does this k still finish in h hours?

Binary search the speed: hi is still a candidate

Keep half-open-feeling bounds on the answer: lo = 1, hi = max(pile), while (lo < hi). Mid is lo + (hi - lo) / 2. If speed mid finishes, a slower speed might also work, so hi = mid — do not drop mid. If it does not finish, you need something strictly faster: lo = mid + 1.

Hours for one pile: integer ceil, (p + k - 1) / k, accumulated in a long so n piles of size 10⁹ cannot wrap an int.

piles = [4, 8, 9, 13]   h = 8   max = 13

lo=1 hi=13 mid=7  hours = 1+2+2+2 = 7  ≤ 8  → hi=7
lo=1 hi=7  mid=4  hours = 1+2+3+4 = 10 > 8  → lo=5
lo=5 hi=7  mid=6  hours = 1+2+2+3 = 8  ≤ 8  → hi=6
lo=5 hi=6  mid=5  hours = 1+2+2+3 = 8  ≤ 8  → hi=5
lo=5 hi=5  done — return 5

The Java is that loop plus the check:

int minEatingSpeed(int[] piles, int h) {
    int lo = 1;
    int hi = 0;
    for (int p : piles) {
        hi = Math.max(hi, p);
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (finishes(piles, h, mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

boolean finishes(int[] piles, int h, int k) {
    long hours = 0;
    for (int p : piles) {
        hours += (p + (long) k - 1) / k;
        if (hours > h) {
            return false;
        }
    }
    return true;
}

Time is O(n log M) where M is the largest pile — log M candidate speeds, each a pass over n piles. Space is O(1). Membership’s inclusive lo <= hi already lives on the algorithms post; this is a lower-bound on the speed axis, so hi = mid is legal.

Note: Ceil with (p + k - 1) / k, not a double. A float ceil will lie on large p. Do not sort piles. Do not use k = 0. Inclusive membership that drops mid on every branch will skip a feasible speed and return one too large.

What interviewers usually poke next

  • Why not sort the piles? Hours add; order does not change the total. Sorting is a different bill for a different question.
  • h equal to n. You must finish a pile per hour, so k is max(pile). The same loop lands there.
  • Return hours for a given k. That is the finishes helper without the search. The problem asked for the minimum k.
  • Overflow. Sum of ceils can exceed Integer.MAX_VALUE. The early hours > h exit is both a speed-up and a guard.

You are done with this problem when you can say, out loud, why trying every speed is correct, why the piles themselves need not be sorted, and why a feasible mid stays a candidate (hi = mid).