Slowest Reading Speed

Anita has piles of pages to read: pile i has pages[i] pages. She has h hours. Each hour she picks one pile and reads up to k pages from it (if the pile has fewer, she finishes it and wastes the rest of that hour). Find the smallest integer k so that she finishes all piles within h hours. (h ≥ number of piles.)

Examples

Example 1

Input:  pages = [3, 6, 7, 11], h = 8
Output: 4

At a speed of 4 pages an hour the piles take 1, 2, 2 and 3 hours — 8 in total, exactly the time she has. At speed 3 the last pile alone needs 4 hours and the total becomes 9, which is too slow, so the smallest workable speed is 4.

Example 2

Input:  pages = [30, 11, 23, 4, 20], h = 5
Output: 30

Constraints

pages holds the size of each pile and h is the number of hours available; h is at least the number of piles.

In one hour she reads at most k pages from a single pile — a smaller pile still uses up the whole hour. Return the smallest k that finishes every pile within h hours.

How to solve it

Hint

“Smallest speed such that …” — if speed k works, every larger speed also works → binary search on k between 1 and max(pages). Checking one k is just summing ceil(pile / k).

Approach: Binary search on the answer

lo = 1, hi = max(pages).
mid = (lo + hi) / 2; hours(mid) = Σ ceil(p / mid).
If hours ≤ h: try smaller (hi = mid); else lo = mid + 1.

Check with the example. At k = 4 the hours are 1 + 2 + 2 + 3 = 8; at k = 3 they are 10.

Complexity: O(n log max(pages)).

The reference solutions in all four languages are in the Solutions tab of the workspace below.