Greedy & Bin Packing

The greedy paradigm

1. Greedy choice property -- making the locally optimal choice doesn't prevent you from finding the globally optimal solution. In other words, you never need to undo a decision.
2. Optimal substructure -- after making a greedy choice, the remaining problem is a smaller instance of the same type of problem.

The classic example: coin change

Interval scheduling

def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])
    selected = []
    last_end = float('-inf')

    for start, end in intervals:
        if start >= last_end:
            selected.append((start, end))
            last_end = end

    return selected

import heapq

def min_rooms(intervals):
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[0])
    heap = []

    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)
        else:
            heapq.heappush(heap, end)

    return len(heap)

Bin packing

The main strategies

def first_fit_decreasing(items, bin_capacity):
    items_sorted = sorted(items, reverse=True)
    bins = []

    for item in items_sorted:
        placed = False
        for i, current_load in enumerate(bins):
            if current_load + item <= bin_capacity:
                bins[i] += item
                placed = True
                break

        if not placed:
            bins.append(item)

    return len(bins), bins

Real-world framing

• Server allocation: You have N tasks with memory requirements and servers with fixed RAM. Minimize the number of servers.
• Container packing: Ship items in boxes of fixed volume. Minimize boxes used.
• Job scheduling with deadlines: Assign jobs to machines where each machine has a capacity per time window.
• Disk partition management: Files of various sizes need to go onto fixed-size partitions.

Multi-dimensional bin packing

def first_fit_decreasing_2d(items, cpu_cap, mem_cap):
    items_sorted = sorted(items, key=lambda x: max(x[0]/cpu_cap, x[1]/mem_cap), reverse=True)
    bins_cpu = []
    bins_mem = []

    for cpu, mem in items_sorted:
        placed = False
        for i in range(len(bins_cpu)):
            if bins_cpu[i] + cpu <= cpu_cap and bins_mem[i] + mem <= mem_cap:
                bins_cpu[i] += cpu
                bins_mem[i] += mem
                placed = True
                break

        if not placed:
            bins_cpu.append(cpu)
            bins_mem.append(mem)

    return len(bins_cpu)

When greedy fails

Quick diagnostic

1. Can I make a choice and never need to undo it? If not, greedy won't work.
2. After making one choice, does the remaining problem look like a smaller version of the same thing? If not, optimal substructure doesn't hold.
3. Can I construct a small counterexample where greedy gives the wrong answer? If yes, you've just proved greedy is wrong. If you can't find one after a couple of minutes, greedy is probably fine, but that's not a proof.

What interviewers expect

• State what the greedy strategy is (e.g., "this sorts by end time and picks non-overlapping intervals")
• Consider whether the greedy choice property holds
• Test it against an edge case or two, especially adversarial ones
• Flag if you think greedy might be wrong and suggest an alternative

The verification checklist

1. What's the greedy criterion? How are we deciding what to pick at each step?
2. Is the sorting correct? Many greedy algorithms depend on processing items in a specific order. Wrong sort key = wrong answer.
3. Does it handle ties? When two items are equally "greedy-optimal," does the tiebreaking matter?
4. Edge cases: empty input, single item, all items identical, items that exactly fill capacity.
5. Counterexample search: try to construct an input where greedy gives a suboptimal answer. Spend at least 30 seconds on this.

Putting it together