Fitting Shelves Problem

Fitting Shelves is a clean greedy problem: you have a wall of a fixed width and two shelf sizes, and you want to cover as much of the wall as possible — leaving the least empty space behind.

The slow way first

You could try every combination of long and short shelves — for each count of long shelves from 0 up to the most that fit, see how much wall is left and how many short shelves fill it. That is a double loop over counts and works, but it does more work than needed.

The question to ask: what gives me the smallest leftover? Bigger shelves cover more wall per piece, so using more long shelves can only help. That nudge toward "prefer the big one first" is the whole greedy idea.

The idea: long shelves first, then shorts

Start with the maximum number of long shelves that fit: wall // long. Whatever wall remains, fill it with short shelves. If the remainder divides evenly by short, the leftover is 0 — perfect. If not, step the long count down by one (freeing up width) and check again. The first count whose remainder fits the short shelves cleanly wins; if none do, keep the smallest leftover you saw.

The key insight: long shelves cover the most ground, so we greedily take as many as we can and only give them up one at a time when the remainder cannot be tiled by short shelves.

Walk through it

Step through the animation. The wall is drawn as 24 unit squares. We compute that at most four long shelves fit (24 // 6 = 4), place all four, and find they cover the wall exactly — leftover 0. The "what if" step shows a width of 22, where four long shelves overflow, so we drop to three long shelves plus one short shelf.

Pseudocode

best = wall                          # worst case: cover nothing
max_long = wall // long              # most long shelves that fit
for n_long from max_long down to 0:
    used = n_long * long
    rest = wall - used               # wall still to cover
    if rest is divisible by short:
        return 0                     # short shelves tile it exactly
    leftover = rest mod short        # uncovered remainder
    keep the smallest leftover seen
return best

The Python solution

def min_leftover(wall, long, short):
    best = wall
    max_long = wall // long
    for n_long in range(max_long, -1, -1):
        used = n_long * long
        rest = wall - used
        if rest % short == 0:
            return 0
        leftover = rest % short
        if leftover < best:
            best = leftover
    return best

• best starts at wall — the leftover if we covered nothing.
• max_long = wall // long is the greedy starting point: the most long shelves that fit.
• The loop counts n_long down from that maximum, giving up one long shelf at a time.
• rest = wall - used is how much wall the short shelves must cover.
• Line 7 is the win condition: if rest % short == 0, short shelves tile the rest exactly and leftover is 0.
• Otherwise leftover = rest % short is the uncovered slice; we remember the smallest one across all counts.

Complexity

The loop runs at most wall // long + 1 times and uses only a few integer variables, so space is constant. In practice you often find a 0 leftover early and return right away.

When this pattern shows up

Practice