🤑 Greedy Algorithms

The Buffet Strategy Analogy

At an all-you-can-eat buffet, you have two strategies:

The Planner: Survey everything, calculate the best combination, then fill your plate optimally.

The Greedy Eater: Take the best-looking thing right now. Whatever looks tastiest at this moment goes on the plate.

The greedy eater makes the locally optimal choice at each step without planning ahead.

Greedy algorithms work the same way.

At each step, pick the option that looks best right now. Don't look ahead, don't reconsider past decisions. Hope that making the best local choice leads to the best overall result.

Why Greedy Often Works

Sometimes a greedy strategy really is optimal.

Making Change (Common Coin Systems)

In some coin systems (like common US coins), a greedy strategy (take the largest coin that fits, repeat) produces an optimal minimum-coin solution.

But this isn't universally true for all possible coin denominations — greedy can fail for other systems (see next section).

When Greedy Fails

Making Change (Unusual Coins)

Coins: [1¢, 3¢, 4¢]. Amount: 6¢. (Toy example)

Greedy approach:

1. Biggest coin that fits? 4¢. Take it. Remaining: 2¢
2. Biggest coin that fits? 1¢. Take it. Remaining: 1¢
3. Take 1¢. Done!

Greedy result: 4 + 1 + 1 = 3 coins

Optimal result: 3 + 3 = 2 coins!

Greedy fails because the locally best choice (4¢) prevents finding the globally best solution (two 3¢ coins).

The Greedy Choice Property

For greedy to work, the problem must have the greedy choice property:

Making the best choice RIGHT NOW
doesn't prevent finding the BEST OVERALL solution.

Think of it like:

• US coins: Taking the biggest coin works for some coin systems (including common US coins)
• Unusual coins: Taking the biggest coin can trap you

If you can prove your problem has this property, a greedy algorithm can be correct.

Classic Greedy Problems

1. Activity Selection

Problem: You have meeting rooms and activities with start/end times. Select the maximum number of non-overlapping activities.

Greedy insight: Pick the activity that ends earliest.

Why? The activity that ends earliest leaves the most time for remaining activities.

Activities: A, B, C, D with start/end times

Greedy (pick earliest ending):
1. Pick the activity that ends earliest
2. Then pick the next activity that starts after that

This greedy choice can be proven optimal for the classic activity selection problem.

2. Fractional Knapsack

Problem: You have a bag with weight capacity. Items have values and weights. Maximize value (you can take fractions of items).

Greedy insight: Sort by value-per-weight ratio, take the highest ratio items first.

This greedy strategy is optimal for the fractional knapsack problem (where you can take partial items).

3. Huffman Coding

Problem: Create the most efficient binary encoding for characters based on frequency.

Greedy insight: Repeatedly merge the two least-frequent symbols (or subtrees).

This produces an optimal prefix code where more frequent symbols tend to get shorter bit patterns.

When to Use Greedy vs Dynamic Programming

The Same Problem, Different Answers

Coin Change with [1, 3, 4] for amount 6:

Greedy thinks: "4 is the biggest that fits → take it!" DP thinks: "Let me consider ALL possible first coins..."

Greedy: 4 + 1 + 1 = 3 coins (wrong!)
DP: Tries 4 first → 3 coins
    Tries 3 first → 3 + 3 = 2 coins (better!)
    Pick the best = 2 coins (correct!)

When greedy choice property doesn't hold, use DP.

Common Greedy Patterns

Pattern 1: Sort and Iterate

Most greedy problems start with sorting:

Activity Selection: Sort by end time
Fractional Knapsack: Sort by value/weight ratio
Job Scheduling: Sort by deadline
Interval Covering: Sort by start time

Pattern 2: Two Pointers

Sometimes greedy works with two pointers moving inward:

Container With Most Water:
- Two pointers at ends
- Greedy: Move the shorter wall (it can only limit us)
- Why? The shorter wall bounds the height; moving it might find taller

Pattern 3: Priority Queue

When the "best" choice changes dynamically:

Huffman Coding: Repeatedly merge the two smallest frequencies
Dijkstra: Repeatedly process the nearest unvisited node (for non-negative edge weights)

How to Prove Greedy Works

Method 1: Exchange Argument

Show that swapping away from greedy makes things worse or equal.

Activity Selection:
  Suppose optimal solution O picks activity X first
  Greedy picks activity G first (ends earliest)

  If X ≠ G, swap X for G in O
  G ends before X, so all activities after still fit
  Solution is at least as good!

Method 2: Greedy Stays Ahead

Show that greedy stays at least as good as any alternative at every step.

Method 3: Counterexample Search

Try to find a case where greedy fails. If you can find one, greedy isn’t correct for that problem in general.

Common Mistakes

Assuming Greedy Works Everywhere

"Just take the biggest/smallest/closest!"

Reality: This often fails. Prove correctness first!

Not Sorting First

Many greedy problems require sorting by a specific criterion. Wrong sort order = wrong answer.

Confusing Fractional and 0/1

Fractional Knapsack: Greedy works (can take partial items)
0/1 Knapsack: Greedy fails (must take whole items or nothing)

FAQ

Q: How do I know if greedy will work?

Try to prove the greedy choice property. If taking the best now CAN'T hurt, greedy works. If you find a counterexample, use DP.

Q: Greedy failed, now what?

Use dynamic programming or backtracking. DP considers all possibilities.

Q: Is sorting part of greedy?

Often yes! Many greedy problems need sorting first (by deadline, ratio, end time).

Q: Why is greedy faster?

It makes one choice per step (often $O(n)$ or $O(n \log n)$ with sorting). DP can be much more expensive depending on the problem.

Q: Can I use greedy for approximations?

Yes! Even when greedy isn't optimal, it often gives a "good enough" answer quickly.

Summary

Greedy algorithms make the locally best choice at each step, hoping it leads to the globally best solution. They're fast and simple but only work when the greedy choice property holds.

Key Takeaways:

• Choose the best option at each step, don’t reconsider
• Works when local optimal leads to global optimal
• Classic examples: activity selection, fractional knapsack, Huffman
• Often requires sorting first
• Faster than DP but not correct for every problem
• Prove correctness with exchange argument or find counterexamples
• When greedy fails, use dynamic programming

Greedy is often the simplest solution when it works - but prove it works first!