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.
shortestRunReaching(crates: list<int>, target: int) → int
C++ needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
int shortestRunReaching(std::vector<int> crates, int target) {
}Worked examples
| Call | Result |
|---|---|
shortestRunReaching(std::vector<int>{2, 3, 1, 2, 4, 3}, 7) | 2 |
shortestRunReaching(std::vector<int>{1, 1, 1, 1}, 4) | 4 |
shortestRunReaching(std::vector<int>{1, 1}, 5) | 0 |
shortestRunReaching(std::vector<int>{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 C++
int shortestRunReaching(std::vector<int> crates, int target) {
if (target <= 0) return 0;
int left = 0, window = 0, best = 0;
for (int right = 0; right < static_cast<int>(crates.size()); right++) {
window += crates[right];
while (window >= target) {
int span = right - left + 1;
if (best == 0 || span < best) best = span;
window -= crates[left];
left++;
}
}
return best;
}