Greedy Algorithms

A greedy algorithm makes the locally optimal choice at every single step, and never looks back to reconsider it — hoping that a sequence of locally-best choices adds up to a globally optimal answer. It's tempting because it's simple and fast, usually O(n log n) or better. The catch: it only produces the correct answer for problems with the greedy choice property — where a locally optimal choice is provably never wrong. This lesson shows one problem where that property holds (so greedy is safe and simple), and one where it doesn't (so greedy quietly gives a wrong answer) — the skill worth building is telling the two apart.

Where Greedy Works: Activity Selection / Interval Scheduling

Problem: given a list of activities, each with a start and end time, select the maximum number of activities that don't overlap (you can only do one at a time).

The greedy rule: sort all activities by end time, ascending. Then walk through them in that order, greedily picking every activity whose start time is at or after the end time of the last activity you picked.

Why this greedy choice is safe: among all activities, the one that finishes earliest can never hurt you to pick first — picking it leaves the maximum possible remaining time for everything else, and any valid solution can be rearranged to include it without reducing the count. That exchange argument is what makes this a real "greedy choice property," not just a fast heuristic that usually works.

# activities is a list of (start, end) tuples
def max_activities(activities):
    activities = sorted(activities, key=lambda a: a[1])  # sort by end time, ascending

    count = 1  # always take the first activity after sorting
    last_end = activities[0][1]

    for start, end in activities[1:]:
        if start >= last_end:  # doesn't overlap the last one picked
            count += 1
            last_end = end

    return count

Time complexity: O(n log n) — dominated by the sort; the single pass afterward is O(n). Space complexity: O(n) for the sorted copy the sort produces (ignoring Timsort's own internal working space) — just one running variable besides that, no table or memo needed, unlike the DP problems from the last two lessons.

Where Naive Greedy Fails: 0/1 Knapsack

Recall 0/1 Knapsack from the previous lesson: choose a subset of items (whole or not at all) to maximize value within a weight capacity. A tempting greedy rule: sort items by value density (value ÷ weight) descending, and keep taking items in that order as long as they still fit.

# Greedy by value density — looks reasonable, but is NOT guaranteed optimal for 0/1 items.
def knapsack_greedy_by_density(weights, values, capacity):
    n = len(weights)
    # sort item indices by value/weight ratio, descending
    indices = sorted(range(n), key=lambda i: values[i] / weights[i], reverse=True)

    total_value = 0
    remaining = capacity
    for i in indices:
        if weights[i] <= remaining:
            total_value += values[i]
            remaining -= weights[i]

    return total_value

Counter-example that breaks it: capacity = 10. Item A: weight 6, value 12 (density 2.0). Item B: weight 5, value 9 (density 1.8). Item C: weight 5, value 9 (density 1.8). Greedy picks A first (highest density) using 6 of the 10 capacity, leaving only 4 — not enough for B or C — for a total value of 12. But picking B and C together costs weight 10 (exactly the capacity) for a total value of 18 — the true optimum, which greedy never even considers because it committed to A and can't undo that choice.

Time complexity: O(n log n) — the sort dominates; the pass afterward is O(n). Space complexity: O(n) for the sorted index list. But the complexity is irrelevant here since the answer can be wrong — this is precisely why runtime alone never justifies an algorithm; correctness comes first.

Recognizing Which Applies