Balanced ranges: the arithmetic before the threads

Divide 0..len among workers and return the half-open ranges as (start, end) pairs.

pub fn balanced_ranges(len: usize, workers: usize) -> Vec<(usize, usize)>

There are no threads in this problem. That is deliberate.

Roughly half of all “my parallel code is wrong” bug reports are off-by-one range bugs, not concurrency bugs. They get blamed on the scheduler because they appear when threads appear. Splitting the arithmetic into its own function means a failing test points at exactly one thing, and it is testable in a way a race never is.

The contract, precisely

• the ranges are half-open: (2, 5) means indices 2, 3, 4;
• together they cover 0..len exactly, with no gaps and no overlaps;
• each end equals the next start;
• sizes differ by at most 1 — the remainder is spread over the first few ranges, one extra element each, not dumped on the last one;
• no empty ranges. If workers > len you return len ranges, not workers of them;
• len == 0 or workers == 0 returns [].

Worked examples:

(10, 3) -> [(0, 4), (4, 7), (7, 10)]     sizes 4, 3, 3
(3, 5)  -> [(0, 1), (1, 2), (2, 3)]      three ranges, not five
(7, 7)  -> [(0,1), (1,2), ... (6,7)]
(0, 4)  -> []

Why not just use div_ceil?

The chunking rule from the previous two problems — one size for everyone, computed with len.div_ceil(workers), short tail at the end — is what slice::chunks does, and it is fine. It is just not balanced.

For (10, 3) it gives sizes 4, 4, 2. The last worker does half the work of the first. That is a 2x load imbalance on three workers, and it gets worse as workers grows: (17, 8) with div_ceil gives 3,3,3,3,3,2,0,0 — two workers with nothing to do at all, which is why the empty-range rule above matters. Balanced splitting gives 3,2,2,2,2,2,2,2.

The rule that produces balance: let base = len / workers and extra = len % workers. The first extra ranges get base + 1 elements and the rest get base. Add them up: extra * (base + 1) + (workers - extra) * base == len. Exactly, with no rounding anywhere.

The lint you must not fight

(len + workers - 1) / workers is the classic hand-rolled ceiling division. clippy::manual_div_ceil has rejected it since 1.83, and it is right to: len + workers - 1 can overflow, this build has overflow checks off, and the wrapped result gives you a nonsense chunk size on exactly the large inputs where you would never notice. usize::div_ceil cannot overflow.

The starter contains that line, so it fails the gate before any test runs — and even after you fix the lint, the starter’s single-size strategy still fails the balance requirement. Both need to go.

A note on usize

Every quantity here is a usize and usize is unsigned. start - 1 when start is 0 does not give you -1; in this release build it wraps to 18446744073709551615 and your program keeps going. Prefer arithmetic that only ever adds, or use checked_sub. This is the single most common source of “impossible” index panics in Rust.