Set Packing

You are handed a pile of sets — committees, teams, time slots, lab reservations — each one a bundle of elements. The rule is simple: you may keep a set only if it shares no element with any other set you keep. The goal: keep as many as possible.

That is set packing. Where its famous twin, set cover, asks you to cover everything with the fewest sets, set packing flips the question: pack the most sets that never collide. One maximizes coverage; the other maximizes disjoint count.

It sounds like the kind of thing you could just eyeball. For a handful of sets, you can. But as the pile grows, the number of valid combinations explodes — and choosing the biggest collision-free family becomes one of the hardest problems we know how to ask.

Below is a collection of sets, each showing the elements it contains. Click a set to add it to your packing — but you can only add a set if it shares no element with the ones you already picked. Try to grab as many as you can.

<p class="hint">{{hint}}</p>
<div id="sets" class="sets"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="greedy" type="button">{{btn_greedy}}</button>
  <button id="optimum" type="button">{{btn_optimum}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</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 .8rem; line-height: 1.45; }
.sets { display: grid; grid-template-columns: repeat(auto-fit, minmax(120px, 1fr)); gap: 10px; margin: .4rem 0; }
.card { border: 2px solid #cdd9e3; background: #f3f7fa; border-radius: 10px; padding: .55rem .6rem; cursor: pointer; transition: all .12s; }
.card:hover { border-color: #1d3557; }
.card .name { font: 700 14px system-ui, sans-serif; color: #1d3557; margin-bottom: .35rem; }
.card .els { display: flex; flex-wrap: wrap; gap: 4px; }
.chip { font: 600 12px ui-monospace, monospace; background: #dde7ef; color: #1d3557; border-radius: 6px; padding: 2px 7px; }
.card.picked { background: #d6f0dd; border-color: #0a7d33; }
.card.picked .name { color: #0a7d33; }
.card.blocked { opacity: .4; cursor: not-allowed; }
.card.blocked .chip { background: #f0d6d6; color: #c92f3c; }
.status { font-size: 1rem; font-weight: 600; margin: .7rem 0 .5rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.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

When you are ready, press Greedy pick to watch a fast, sensible strategy — always grab the smallest available set first — and then Show optimum to reveal the true best answer found by exhaustive search. Notice the trap: the greedy choice often locks in a set that blocks two better ones, and ends up short. Checking that a chosen family is collision-free is instant; finding the largest one is where the difficulty lives.

How hard is set packing, really? Here is the precise status.

• Checking is easy. Given a proposed family of sets, verifying that no two overlap and counting them takes seconds. That puts the decision version ("can I pack at least k disjoint sets?") squarely in NP.
• It is NP-complete. Set packing's decision form is one of Richard Karp's original 21 NP-complete problems (1972). The optimization version — pack the maximum number — is NP-hard.
• It is independent set in disguise. Build a graph with one node per set and an edge between any two sets that share an element. A collision-free packing is exactly an independent set in that graph, so the two problems are computationally the same.
• The mirror of set cover. Set cover minimizes sets to cover all elements; set packing maximizes disjoint sets. Same raw materials, opposite objective — and both are hard.
• Even approximating is hard. For sets of unbounded size, no polynomial algorithm can guarantee getting close to the optimum unless P = NP; the best known guarantees degrade as the sets grow.

So the greedy gap you saw is not a coding mistake. The instant a real instance grows past a toy size, finding the maximum packing is an instance of the same wall behind P vs NP.

"Choose as many non-conflicting options as possible" is a shape that shows up everywhere once you learn to see it:

• Combinatorial auctions: bidders bid on bundles of items; the auctioneer wants to accept the most valuable set of bids that share no item — a weighted set packing.
• Conflict-free scheduling: pick the most meetings, jobs, or lab reservations that never demand the same resource at the same time.
• Wireless channel assignment: assign frequencies to the largest group of transmitters whose coverage areas do not interfere.
• Resource allocation: hand out servers, vehicles, or rooms so that the most requests are honored without double-booking.

Each of these is the same engine as the puzzle above. Learn set packing and you have met a whole family — it sits beside set cover and independent set at the heart of combinatorial optimization.

Set packing is one of those problems that hides its teeth behind a friendly question: which non-overlapping sets should I keep? Checking any answer is trivial, but finding the largest collision-free family is NP-hard — a member of Karp's original 1972 list, equivalent to independent set, the exact mirror of set cover.

That is why the greedy pick keeps coming up short, and why real systems lean on clever heuristics and approximations rather than guaranteed optima. Behind the tidy sets and the satisfying click of a non-overlapping choice sits P vs NP — the same frontier that decides whether "pack the most" will ever be easy.