Greedy & Bin Packing

Greedy & bin packing covers problems where local optimization leads to good-enough global solutions: resource allocation, interval scheduling, packing items into containers. The AI loves to suggest greedy — often correctly, sometimes dangerously.

What it solves

Problems where you repeatedly make the locally best choice and never revisit it: schedule as many non-overlapping meetings as possible (earliest finish wins), pack items into bins with weights and capacities, assign jobs to stations, pick the next best move in a sequence.

Recognition signals

• "Maximize the number of / fit as many as possible"
• "Bin/capacity/weight", "pack", "load", "container", "slot"
• "Non-overlapping intervals", "scheduling", "earliest deadline"
• "Greedy is optimal here" vibes — or a hint that near-optimal is acceptable
• "It's okay if it's not perfectly optimal" (a license for greedy)

The approach

The classic moves:

The central judgment call: is greedy provably correct for this problem, or is the interview just tolerating near-optimal? That's a decision you make — and narrate — before prompting. When greedy isn't provably optimal and optimality matters, that's a hint for DP instead.

What to tell the AI

Implement greedy interval scheduling: sort intervals by end time, then greedily select each interval whose start is after the last selected interval's end. Return the selected intervals.

What to verify

• The sort key — the AI sorts by start when the rule needs end, or uses the wrong comparator. This is the #1 bug.
• Tie-breaking — decide how ties resolve; the AI will invent one.
• Greedy-when-you-needed-DP — check the AI didn't accept greedy in a case where it's provably wrong (e.g., weighted interval scheduling).
• Packing order — packing items in input order instead of sorted order changes fill rates.
• Proof vs. assumption — a "greedy works here" comment without justification is a red flag; ask yourself why.

Worked micro-example

Intervals [1,3],[2,4],[3,6]. Sort by end: [1,3],[2,4],[3,6]. Pick [1,3], then the next whose start ≥ 3 → [3,6]. Result: 2 intervals. Greedy by earliest finish is optimal for maximizing count — narrate that "the exchange argument holds because an earliest-finishing interval leaves maximum remaining room."

Practice problems

Try these: Inventory Packer (multi-bin packing with weights), Kitchen Orders (priority + station assignment), Maximize Unique Characters (greedy selection combined with backtracking).