Given a load limit, how do you check in one pass whether n contiguous batches fit k workers?

## The setup An ingestion pipeline receives sensor batches in a fixed order — `b[0], b[1], ..., b[n-1]`, each a count of records. You have `k` workers. Because batches are consumed in stream order, each worker must take one **contiguous** run of them, and the pipeline finishes as slowly as its busiest worker. So the objective is to place `k - 1` cut points so as to minimize the largest run total. Searching directly for that best split is awkward; **verifying** a proposed maximum load is easy. That asymmetry is what makes this a binary-search-on-the-answer problem, and the verifier is the piece worth getting exactly right. ## The check ``` // b holds batch sizes in fixed order; each worker takes a contiguous run feasible(b, k, limit): if limit < max(b): return false workers = 1 load = 0 for i in 0..length(b)-1: if load + b[i] <= limit: load = load + b[i] else: workers = workers + 1 load = b[i] return workers <= k ``` Read it as: one worker is open, its load starts empty, and every batch either joins the open worker or forces a new one. The function answers a single boolean question — "can `k` workers each stay at or below `limit`?" — and nothing else. It does not compute the answer, it scores one candidate. ## Why greedy is optimal here The instinct that greedy might be too crude is worth addressing directly, because interviewers probe it. Take any valid split into at most `k` runs under `limit`, and compare it with the greedy split, scanning from the left. Greedy's first cut is at least as far right as the other split's first cut, because greedy stops only when adding the next batch would exceed `limit`. Push the other split's cut rightward to match; the resulting split is still valid, because the earlier run stays within the limit by construction and the later run only shrinks. Repeat down the sequence: greedy's every cut is at least as far right as the alternative's, so greedy uses no more runs than any valid split. Therefore greedy finding more than `k` runs proves no split under `limit` exists. This argument leans on all values being non-negative. If batches could contribute negative load, moving a cut rightward would not be safely monotone and the greedy check would break. ## The boundary case that fails silently Drop the first line and the function still runs — that is what makes the bug dangerous. Suppose one batch is larger than `limit`. On reaching it, `load + b[i] <= limit` is false, so the code opens a new worker and sets `load = b[i]`, which is already over the limit. No check ever rejects it. With few enough batches the worker count still lands at or below `k`, and the function returns true for a limit that is physically impossible. The search then converges below the real answer. Two clean fixes exist: keep the explicit guard shown above, or start the search's lower bound at `max(b)` so an infeasible-by-construction limit is never proposed in the first place. Doing both is not wasteful — the guard makes the check correct in isolation, which matters if it is ever called from anywhere else. ## Cost One pass, so `O(n)` time; two scalars, so `O(1)` extra space. Combined with the roughly `log2(sum(b))` halvings the surrounding search performs, the whole solution is `O(n log(sum(b)))`. Note that the `max(b)` guard is itself a scan — compute it once before the search rather than recomputing it inside every call, or the check silently doubles its constant factor. ## Tracing it Take `b = [7, 2, 5, 10, 8]`, `k = 2`, `limit = 18`. Worker 1 accumulates 7, 9, 14; adding 10 would reach 24, so worker 2 opens with 10 and then takes 18. Two workers, so 18 is feasible. Now `limit = 15`: worker 1 reaches 14, worker 2 opens with 10, adding 8 would reach 18, so worker 3 opens. Three workers, so 15 is infeasible. The true answer lies between, and being able to run these traces aloud is most of what the interviewer is checking. ## Variations that keep the same skeleton Swap "workers" for nights, machines, trucks or buffers and nothing structural changes: a fixed-order sequence, an indivisible unit, a per-container ceiling, and a count to compare against. If the order is *not* fixed — if you may reorder items freely — the check is no longer a greedy sweep and the underlying problem is much harder; recognizing that contiguity is what makes the linear check valid is the mark of a candidate who understands the technique rather than the template.