Bin Packing (First-Fit Decreasing)

Bin Packing asks: given items of different sizes and bins of fixed capacity, how few bins do you need to hold everything? The exact answer is NP-hard, but a simple greedy rule gets remarkably close — and it is a classic interview warm-up for greedy thinking.

The slow way first

Finding the provably minimum number of bins is NP-hard — to be certain you would have to try essentially every way of splitting items across bins, which is exponential. For an interview, that is a dead end.

So we ask a different question: what is a fast rule that does well in practice? The greedy family of first-fit heuristics answers that — and sorting the items first makes them noticeably better.

The idea: first-fit, biggest item first

Sort the items descending, then process them one at a time. For each item, scan the open bins left to right and drop it into the first bin that still has room. If no open bin fits, open a new bin. That is it.

Why descending? Big items are the hardest to place, so we commit them while bins are empty; the small leftovers then slot into the gaps the big items leave behind. This is First-Fit Decreasing (FFD), and it is guaranteed to use no more than about 11/9 · OPT + 1 bins.

Walk through it

Step through the animation with items = [7, 6, 5, 4, 3], cap = 10. The first three items each need a fresh bin. Then 4 finds room in Bin 1 (which had 6), and 3 finds room in Bin 0 (which had 7) — filling earlier gaps instead of opening new bins. Total: 3 bins.

Pseudocode

sort items from largest to smallest
bins = []                       # remaining room in each open bin
for each item x:
    placed = false
    for each open bin b (left to right):
        if room in b >= x:
            put x in b; reduce its room by x
            placed = true; stop scanning
    if not placed:
        open a new bin with room (cap - x)
return number of bins

The Python solution

def first_fit_decreasing(items, cap):
    items = sorted(items, reverse=True)
    bins = []                       # remaining room per bin
    for x in items:
        placed = False
        for b in range(len(bins)):
            if bins[b] >= x:
                bins[b] -= x
                placed = True
                break
        if not placed:
            bins.append(cap - x)
    return len(bins)

• sorted(items, reverse=True) puts the biggest items first — the decreasing in FFD.
• bins stores the remaining room in each open bin, not the items themselves.
• The inner loop is the first-fit scan: stop at the first bin whose room is at least x.
• break is important — we take the first fit, not the best one.
• If the scan finishes with placed still False, we open a new bin holding cap - x.

Complexity

The placement loop dominates: in the worst case every item scans every open bin, so O(n²). The bins list uses O(n) space (at most one bin per item). Faster O(n log n) variants exist using a balanced tree of bin capacities, but the n² version is the expected interview answer.

When this pattern shows up

Practice