The challenge
Find the smallest integer speed allowing all piles to be eaten in at most h hours. Each hour is spent on one pile.
Nonempty positive integer piles, each ≤ 10⁹. Return −1 when h < number of piles. Sums of counts fit 64-bit integers.
Example
[3, 6, 7, 11], h = 8 → speed 4, needing 1 + 2 + 2 + 3 hours.
Use the walkthrough below to inspect the input and each state change.
See Minimum feasible speed, step by step
Inspect the comparison, the invariant, and the next boundary.
Answer-space searchh = 8
Tested candidate / qualifying inputResolved positionParameters shown above
- Left
- 1
- Middle
- —
- Right
- 11
Step 01 / 6
Search the answer range
The candidate is a number, rather than an input index. Keep the smallest feasible value.
left = 1; right = 11Recorded result so far
Not resolved
View exact input
Input: [3,6,7,11] · h = 8
Put it into code
The hours needed never increase as speed rises. Search the first speed whose total ceiling-divided hours is within budget.
Indices are zero-based. C++ uses C++17 or later.
def minimum_speed(piles, h):
# Nonempty positive piles; h >= 0. One pile per hour.
if h < len(piles):
return -1
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
hours = sum((pile + mid - 1) // mid for pile in piles)
if hours <= h:
right = mid
else:
left = mid + 1
return left#include <algorithm>
#include <vector>
int minimum_speed(const std::vector<int>& piles, long long h) {
if (h < static_cast<long long>(piles.size())) return -1;
int left = 1, right = *std::max_element(piles.begin(), piles.end());
while (left < right) {
int mid = left + (right - left) / 2;
long long hours = 0;
for (int pile : piles) hours += (static_cast<long long>(pile) + mid - 1) / mid;
if (hours <= h) right = mid;
else left = mid + 1;
}
return left;
}