The quickest way to fill the order
Crates come off a belt in a fixed order. A picker wants the shortest unbroken run of crates that together hold at least what the order needs.
- Only consecutive crates count — the run cannot skip one.
- Every crate holds zero or more units; none are negative.
- Return the number of crates in the shortest run that reaches the target.
- If no run reaches it, return 0.
- A target of zero or less is already met, so the answer is 0.
shortest_run_reaching(crates: list<int>, target: int) → int
Where you start
def shortest_run_reaching(crates: list[int], target: int) -> int:
Worked examples
| Call | Result |
|---|---|
shortest_run_reaching([2, 3, 1, 2, 4, 3], 7) | 2 |
shortest_run_reaching([1, 1, 1, 1], 4) | 4 |
shortest_run_reaching([1, 1], 5) | 0 |
shortest_run_reaching([8], 8) | 1 |
Hint
Grow the window on the right while it falls short, and shrink it from the left the moment it is enough. Each end only ever moves forward.
Reference solution in Python
def shortest_run_reaching(crates: list[int], target: int) -> int:
if target <= 0:
return 0
left = 0
window = 0
best = 0
for right, crate in enumerate(crates):
window += crate
while window >= target:
span = right - left + 1
if best == 0 or span < best:
best = span
window -= crates[left]
left += 1
return best