The Greedy Paradigm — Algorithms Course

What you'll learn

A greedy algorithm builds a solution one step at a time, always taking the choice that looks best right now — and never reconsidering. When it works, it's wonderfully simple and fast. The catch: it doesn't always work, so you must learn to tell when it does.

By the end you'll be able to:

Describe the greedy strategy
Check for the greedy-choice property and optimal substructure
Solve interval scheduling greedily
Prove a greedy algorithm optimal with an exchange argument

The greedy idea

At each step, commit to the locally optimal choice and move on. No backtracking, no lookahead. This is the opposite of dynamic programming, which considers many combinations — greedy bets that a sequence of local optima yields a global optimum. Sometimes that bet is provably safe; sometimes it's wrong.

When greedy works

A greedy algorithm is correct when the problem has both:

Greedy-choice property: a globally optimal solution can be reached by making the locally optimal choice at each step.
Optimal substructure: an optimal solution contains optimal solutions to its subproblems (it shares this with DP).

Interval scheduling

The textbook success story: given activities with start and finish times, select the most that don't overlap. The winning greedy rule is earliest finish time first — it frees the room as soon as possible for the rest:

Activity selection

1–4

3–5

0–6

5–7

3–9

5–9

6–10

8–11

Sorted by finish time; green = chosen (earliest finish that still fits).

Pick the activity that finishes earliest, skip everything that overlaps it, repeat.

Language

max_activities.py

def max_activities(intervals):
    intervals.sort(key=lambda iv: iv[1])   # by finish time
    chosen, last_end = [], float("-inf")
    for start, end in intervals:
        if start >= last_end:              # compatible?
            chosen.append((start, end))
            last_end = end                 # greedy choice
    return chosen

The exchange argument

Why is "earliest finish" optimal? The exchange argument: take any optimal solution and show you can swap its first activity for the greedy one (which finishes no later) without losing feasibility or count. Repeating the swap turns the optimal solution into the greedy one — so greedy is at least as good, hence optimal.

Key idea

Exchange arguments are the standard way to prove a greedy algorithm correct: show any optimal solution can be transformed step by step into the greedy one without getting worse.

When greedy fails

Greedy is seductive but often wrong. For 0/1 knapsack, grabbing the highest value-per-weight item first can miss the best combination. For coin change with arbitrary denominations, greedy can use more coins than necessary (e.g. coins {1, 3, 4} making 6: greedy picks 4+1+1, optimal is 3+3). When greedy fails, reach for dynamic programming.

Watch out

Never assume greedy is correct because it's obvious — prove it, or find a counterexample. A single failing case means you need DP (Phase 5) instead.

Recap & quick check

Key takeaways

Greedy makes the locally optimal choice at each step and never reconsiders.
It's correct when the problem has the greedy-choice property and optimal substructure.
Interval scheduling: pick earliest finish time first — provably optimal.
Prove greedy optimal with an exchange argument.
Greedy fails for 0/1 knapsack and arbitrary coin change — use DP there.

Quick check

1. What defines a greedy algorithm?

2. Which greedy rule optimally solves interval scheduling?

3. How do we usually prove a greedy algorithm optimal?

4. For which problem is greedy NOT guaranteed optimal?

Let's put greedy to work on some of its greatest hits. Next up: Module 14 — Classic Greedy Algorithms.