Real-time renderers batch many small textures (sprites, glyphs, UI icons, material maps) into one big TEXTURE ATLAS so the GPU can draw them all with a single texture bind instead of swapping textures per draw call. Packing differently-sized rectangles into the smallest space without overlap is bin packing; a SHELF packer is the simplest practical strategy: lay rectangles left-to-right along a horizontal "shelf," and once one doesn't fit, start a new shelf below the tallest rectangle placed on the current one.

Implement pack_shelves(rects, atlas_width):

1. Sort rects by height, TALLEST FIRST -- a standard shelf-packing heuristic that reduces wasted vertical space per shelf.
2. Walk the sorted list, placing each rect at the current shelf position (shelf_x, shelf_y). If it doesn't fit on the current shelf (shelf_x + width > atlas_width), start a new shelf below the current one: shelf_y += (the current shelf's tallest rect so far), shelf_x resets to 0.
3. Return every rect's placement plus the total atlas height used.

Raise ValueError if any single rect's width exceeds atlas_width (it could never fit on any shelf, regardless of atlas height).

Example

rects = [("a", 4, 2), ("b", 3, 3), ("c", 5, 1), ("d", 2, 2)]
pack_shelves(rects, atlas_width=6)
# sorted tallest-first: b(h=3), a(h=2), d(h=2), c(h=1)
# -> ({"b": (0, 0), "a": (0, 3), "d": (4, 3), "c": (0, 5)}, 6)

Constraints

• Rects are placed in TALLEST-FIRST order (ties keep their original relative order -- a stable sort).
• No two placed rects may overlap, and none may extend past atlas_width horizontally.
• atlas_height returned is exactly shelf_y + shelf_height of the last shelf used -- the tightest height that actually contains every placement, not a rounded-up or padded value.

Real-world grounding

• Jukka Jylänki's RectangleBinPack -- the reference implementation behind the widely-cited "A Thousand Ways to Pack the Bin" survey of rectangle bin-packing heuristics, and a common reference point for real texture-packer tools -- implements exactly this shelf strategy (ShelfBinPack) alongside guillotine and max-rects variants: ShelfBinPack.cpp, GuillotineBinPack.cpp (a different, more space-efficient but more complex strategy that recursively splits leftover free space instead of stacking shelves).

Real texture packers often add power-of-two atlas dimensions (a GPU mipmapping constraint), rotation (packing a rect sideways if that fits better), and a choice among several placement heuristics (best-fit, guillotine, max-rects) that all beat plain shelf packing's wasted space -- this exercise implements the simplest member of that family, the one every more elaborate packer is still ultimately compared against.