Greedy Algorithms & When They Work

Jr Codex DSA Notes

Level: Advanced Prerequisites: Chapter 3 Time to complete: ~25 minutes

Table of Contents

1. What Is a Greedy Algorithm?
2. The Greedy Choice Property
3. Where Greedy Works: Activity Selection
4. Where Greedy Fails: 0/1 Knapsack
5. Why the Difference? Local vs. Global Optimality
6. A Decision Checklist: Greedy or DP?
7. Summary & Next Steps

1. What Is a Greedy Algorithm?

A greedy algorithm builds a solution step by step, at each step making the choice that looks best right now, and never reconsidering that choice later. There's no backtracking (Module 4), no trying multiple options, no table of subproblem answers (this module's Chapters 1-3) — just one pass, one locally-best decision at a time.

This makes greedy algorithms attractively simple and fast — usually O(n log n) (dominated by an initial sort) or O(n). The catch, covered in this chapter, is that greedy is only correct on problems with a specific structural property. Applied to the wrong problem, it produces a fast, confident, wrong answer — which is more dangerous than an algorithm that's merely slow.

2. The Greedy Choice Property

A problem is greedy-solvable when it has the greedy choice property: a globally optimal solution can always be reached by making the locally optimal choice at each step, without needing to revisit it later. Not every optimization problem has this property — and telling which ones do is the actual skill, not the greedy algorithms themselves (which are usually short and simple once you know one applies).

3. Where Greedy Works: Activity Selection

Problem: Given a list of activities, each with a start and end time, select the maximum number of non-overlapping activities you can attend (one room, one person).

Greedy strategy: Always pick the activity that ends earliest among the remaining valid options. Sort by end time once, then scan once, taking any activity whose start time is at or after the last activity's end time.

def activity_selection(activities):
    # activities: list of (start, end) tuples
    activities = sorted(activities, key=lambda a: a[1])   # sort by END time
    selected = [activities[0]]
    last_end = activities[0][1]
 
    for start, end in activities[1:]:
        if start >= last_end:          # doesn't overlap with the last pick
            selected.append((start, end))
            last_end = end
 
    return selected
    # O(n log n) — dominated by the sort; the scan itself is O(n)

Why "earliest end time" is provably safe: picking the activity that finishes soonest always leaves the most possible room for everything that comes after — no other first choice can ever leave strictly more remaining time. That's the greedy choice property holding here: today's locally-best pick never has to be undone later.

4. Where Greedy Fails: 0/1 Knapsack

Apply the same intuition to 0/1 Knapsack from Chapter 3: greedily take items in order of best value-per-weight ratio first, as long as they fit.

def knapsack_greedy_WRONG(weights, values, capacity):
    items = sorted(zip(weights, values), key=lambda x: x[1] / x[0], reverse=True)
    total_value = 0
    remaining = capacity
 
    for weight, value in items:
        if weight <= remaining:
            total_value += value
            remaining -= weight
    return total_value
    # Fast — O(n log n) — but NOT guaranteed correct for 0/1 knapsack!

Counter-example: weights = [1, 3, 4], values = [15, 20, 30], capacity = 4 (the exact example from Chapter 3, Section 3). Value-per-weight ratios: item 1 = 15, item 2 ≈ 6.67, item 3 = 7.5. Greedy takes item 1 (ratio 15, weight 1, remaining capacity 3), then item 3 doesn't fit (weight 4 > 3), then item 2 fits (weight 3, ratio 6.67) → total = 15 + 20 = 35. That happens to match the correct DP answer here — but change the numbers slightly (say values = [15, 20, 30], weights = [1, 3, 4], capacity = 5) and greedy takes item 1 (value 15, remaining 4), then item 3 doesn't fit as cleanly against item 2+3 combos — greedy commits to a locally-attractive item early and can't "put it back" once a better combination appears, whereas the DP table in Chapter 3 explicitly considers every skip/take combination and can't make that mistake.

Why it fails here: taking the best ratio item first can lock up capacity that would have been better spent combining two other items whose combined value exceeds what the greedy pick allows for later. Because you can't take a fraction of an item (0/1, not fractional), an early greedy choice can permanently close off the actually-optimal combination — there's no way to "undo" it the way DP implicitly considers by keeping every subproblem's answer in the table.

5. Why the Difference? Local vs. Global Optimality

The general lesson: greedy works when an early choice never closes off a better combination later — only a strictly worse (or equal) one. When earlier choices can foreclose a better combination of later choices, you need DP's exhaustive (but memoized) consideration of every option instead.

6. A Decision Checklist: Greedy or DP?

1. Can you prove (or strongly convince yourself) that the locally-best choice never needs to be revisited? → Greedy is likely provably correct.
2. Does taking one option change what combinations remain feasible for the rest (like knapsack's shared capacity)? → Likely needs DP.
3. Is there a well-known "fractional" relaxation of the problem where greedy does work (as with fractional knapsack in Chapter 5)? If your actual problem requires whole/indivisible choices, be suspicious of applying that same greedy strategy.
4. When in doubt: code the greedy version, then test it against a brute-force or DP solution on small random inputs. If they ever disagree, greedy is wrong for this problem — this is the single most reliable way to catch a broken greedy assumption before an interview or production bug does.

7. Summary & Next Steps

Key Takeaways

• Greedy algorithms make one irrevocable, locally-best choice per step — fast, but only correct when the problem has the greedy choice property.
• Activity Selection is a textbook case where greedy is provably correct: picking the earliest-ending activity never forecloses a better combination later.
• 0/1 Knapsack is a textbook case where greedy fails: an early best-ratio pick can lock up capacity that a better combination needed, and greedy can never undo that choice.
• When unsure whether a problem is greedy-solvable, test the greedy solution against a DP or brute-force solution on small inputs before trusting it.

Concept Check

1. What is the "greedy choice property," in your own words?
2. Why is "earliest end time first" provably safe for Activity Selection, but "best value/weight ratio first" is not safe for 0/1 Knapsack?
3. What's a practical way to check whether a greedy strategy you've come up with is actually correct?

Next Chapter

→ Chapter 5: Classic Greedy Problems

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index