Introduction

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.

Try It: Pack the Most

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">Each card is a set of elements. Click a set to add it to your packing — but only if it shares <b>no element</b> with the sets you already picked. Grab as many disjoint sets as you can, then compare with greedy and the true optimum.</p>
<div id="sets" class="sets"></div>
<div class="status" id="status">Picked: 0 sets.</div>
<div class="btns">
  <button id="greedy" type="button">Greedy pick</button>
  <button id="optimum" type="button">Show optimum</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// SET PACKING: choose the most sets so that no two share an element.
// Checking a chosen family (pairwise-disjoint?) is instant; finding the LARGEST
// such family is NP-hard (Karp, 1972) — equivalent to Maximum Independent Set. This instance is built so a natural greedy (smallest-set-first) is NOT optimal.
const SETS = [
  { name: 'A', els: [1, 2, 3] },     // big, in the optimum
  { name: 'B', els: [4, 5, 6] },     // big, in the optimum
  { name: 'C', els: [7, 8] },        // small, in the optimum
  { name: 'X', els: [3, 4] },        // SMALL trap: shares 3 with A and 4 with B
  { name: 'Y', els: [9, 10] }        // small, in the optimum
];
const overlap = (x, y) => x.els.some(e => y.els.includes(e));

let picked = new Set();   // indices the player chose
let highlight = null;     // 'greedy' | 'optimum' | null

function disjointWithPicked(i, chosen) {
  for (const j of chosen) if (j !== i && overlap(SETS[i], SETS[j])) return false;
  return true;
}
function render() {
  const wrap = document.getElementById('sets'); wrap.innerHTML = '';
  SETS.forEach((s, i) => {
    const d = document.createElement('div');
    const isPicked = picked.has(i);
    const blocked = !isPicked && !disjointWithPicked(i, picked);
    d.className = 'card' + (isPicked ? ' picked' : '') + (blocked ? ' blocked' : '');
    d.innerHTML = fmt('<div class="name">Set %name%</div><div class="els">%map%</div>', { name: s.name, map: s.els.map(e => '<span class="chip">' + e + '</span>').join('') });
    d.addEventListener('click', () => {
      if (picked.has(i)) { picked.delete(i); }
      else { if (!disjointWithPicked(i, picked)) { flash(fmt('Set %name% shares an element — cannot add.', { name: s.name }), 'bad'); return; } picked.add(i); }
      highlight = null; render(); report();
    });
    wrap.appendChild(d);
  });
}
function report() {
  setStatus(fmt('Picked: %size% disjoint set%v%.', { size: picked.size, v: picked.size === 1 ? '' : 's' }), picked.size >= 3 ? 'ok' : '');
}
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }
function flash(t, cls) { setStatus(t, cls); }

// Greedy: repeatedly take the smallest available set disjoint from what's chosen.
function greedy() {
  const chosen = new Set();
  const order = SETS.map((s, i) => i).sort((a, b) => SETS[a].els.length - SETS[b].els.length || a - b);
  for (const i of order) if (disjointWithPicked(i, chosen)) chosen.add(i);
  picked = chosen; highlight = 'greedy'; render();
  setStatus(fmt('Greedy (smallest-first) packed %size% sets: %sort%.', { size: chosen.size, sort: [...chosen].map(i => SETS[i].name).sort().join(', ') }), 'bad');
}
// Optimum: brute-force every subset, keep the largest pairwise-disjoint one.
function optimum() {
  let best = [];
  for (let mask = 0; mask < (1 << SETS.length); mask++) {
    const sub = [];
    for (let i = 0; i < SETS.length; i++) if (mask & (1 << i)) sub.push(i);
    let ok = true;
    for (let a = 0; a < sub.length && ok; a++)
      for (let b = a + 1; b < sub.length; b++)
        if (overlap(SETS[sub[a]], SETS[sub[b]])) { ok = false; break; }
    if (ok && sub.length > best.length) best = sub;
  }
  picked = new Set(best); highlight = 'optimum'; render();
  setStatus(fmt('Optimum packs %length% sets: %sort%. Greedy gets only 3.', { length: best.length, sort: best.map(i => SETS[i].name).sort().join(', ') }), 'ok');
  console.log('Optimum:', best.map(i => SETS[i].name).join(','), '(size', best.length + ')');
}
document.getElementById('greedy').addEventListener('click', greedy);
document.getElementById('optimum').addEventListener('click', optimum);
document.getElementById('reset').addEventListener('click', () => { picked.clear(); highlight = null; render(); report(); });
render(); report();
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/set-packing/Content licensed under CC BY-NC 4.0.