Strip Packing

Imagine a long roll of fabric, paper, or sheet metal. Its width is fixed, but its length is as long as you need. You have a pile of rectangular pieces to cut from it, and every piece must fit without overlapping or being rotated past the rules. The question is simple to state: how do you arrange them so the roll you use is as short as possible?

That is the strip packing problem. You are not allowed to make the strip wider — only longer — so all the cleverness goes into how you nest the rectangles side by side and stack them up. Waste any space and you waste material; in a factory that runs all day, those gaps cost real money.

It looks like a tidy game of Tetris with no time pressure. And yet, finding the genuinely shortest arrangement is one of the hardest kinds of problems in all of computer science. Strip packing is the two-dimensional cousin of bin packing — and it inherits the same intractability.

Below is a strip of fixed width and a fixed set of rectangles. Two strategies place the same pieces. The shelf heuristic is the simple, fast one: lay pieces left to right on a row, and when the next piece won't fit, start a new shelf on top. The tight packing slides each piece down and left into the lowest gap it can reach.

<p class="hint">{{hint}}</p>
<div class="stage">
  <div class="panel">
    <div class="cap">{{cap_shelf}} <span id="h-shelf" class="badge">–</span></div>
    <canvas id="shelf" width="220" height="320"></canvas>
  </div>
  <div class="panel">
    <div class="cap">{{cap_tight}} <span id="h-tight" class="badge">–</span></div>
    <canvas id="tight" width="220" height="320"></canvas>
  </div>
</div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="run-shelf" type="button">{{btn_shelf}}</button>
  <button id="run-tight" type="button">{{btn_tight}}</button>
  <button id="run-both" type="button">{{btn_both}}</button>
  <button id="shuffle" type="button" class="ghost">{{btn_shuffle}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.stage { display: flex; gap: 1.2rem; flex-wrap: wrap; }
.panel { text-align: center; }
.cap { font: 600 14px system-ui, sans-serif; color: #1d3557; margin-bottom: .35rem; }
.badge { display: inline-block; min-width: 2.4em; padding: .05rem .45rem; margin-left: .3rem;
         background: #e8eef3; color: #1d3557; border-radius: 6px; font-weight: 700; }
canvas { background: #f4f6f8; border: 2px solid #1d3557; border-radius: 6px; }
.status { font-size: 1rem; font-weight: 600; margin: .7rem 0 .5rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Press the buttons and watch the total height each method needs. The shelf method is quick and easy to reason about, but it leaves ragged gaps above short pieces. The tighter packing reuses that wasted space and ends up lower. Now imagine dozens of pieces in dozens of sizes — the number of possible arrangements explodes, and no fast method is guaranteed to find the true minimum.

How hard is it to find the shortest possible strip? Genuinely hard.

• Checking a proposed layout is easy: confirm no two rectangles overlap, none spills past the fixed width, and read off the total height.
• Searching for the best layout is the trouble. Each rectangle can go in many positions; the arrangements multiply combinatorially, and there is no known shortcut.
• It's NP-hard. Strip packing contains bin packing as a special case — make every rectangle the same height, and packing them into minimum strip length is exactly bin-packing items into bins. Since bin packing is strongly NP-hard, so is strip packing, and its decision version ("does a packing of height at most H exist?") is NP-complete.
• No exact polynomial algorithm is known, and finding one would settle P vs NP. In practice we use approximation algorithms with provable guarantees: classic results give arrangements within a constant factor of optimal, and the best known asymptotic ratio for the offline problem approaches 5/3.

So the comfortable feeling that "you could just shuffle the pieces a bit" is an illusion. Past a handful of rectangles, "shuffle until perfect" means searching an exponential haystack — the same wall behind every NP-hard problem.

"Fit these shapes into a fixed-width space using as little length as possible" describes a startling number of real jobs:

• Cutting stock: textile, paper, glass and metal are sold in fixed-width rolls or sheets; minimizing length cut is minimizing waste. This is the industrial heart of cutting stock.
• Chip and PCB layout: placing rectangular blocks on silicon of fixed width while shrinking the chip's height is a strip-packing problem with billions of dollars riding on the gaps.
• Advertising and image layout: fitting banners or photos of various sizes into a fixed-width column with minimal scroll length is the same shape of problem.
• Scheduling: a rectangle's width can be "machines used" and its height "time taken" — packing them tightly is scheduling parallel jobs to finish as early as possible.

Learn why strip packing is hard and you have met a whole family of placement and scheduling problems that quietly run modern industry.

Strip packing hides a familiar twist: it is effortless to check a layout and brutally hard to find the best one. Because it contains bin packing, it is NP-hard, and a fast exact algorithm would topple P vs NP. So in the real world we settle for clever heuristics and approximations that come close enough.

The next time you watch a cutting machine nest shapes onto a roll, or a layout engine arrange tiles on a page, remember: it is not chasing perfection. It is making peace with an intractable problem — and doing a remarkably good job of getting close.