Chapter 20 — Greedy Algorithms

Chapter 20 — Greedy Algorithms

Hey everyone! Welcome back to Namaste DSA!

A greedy algorithm makes the choice that looks best right now, and never reconsiders. When it works, it's beautifully simple and fast. The catch: greedy doesn't always give the best overall answer — so the real skill is knowing when you can trust it.

What we will cover:

• The greedy idea
• When greedy works (and when it fails!)
• Activity selection
• Coin change — greedy vs reality
• Greedy vs Dynamic Programming
• Interview Questions

---

1. The Greedy Idea

┌─────────────────────────────────────────────────────────────┐
│   At each step, grab the LOCALLY best option and commit.    │
│   Never look back, never undo (unlike backtracking).        │
│                                                             │
│   FAST and SIMPLE — but only correct if local optimum       │
│   leads to the global optimum.                              │
└─────────────────────────────────────────────────────────────┘

---

2. When Greedy Works — and When It Fails

Greedy is provably correct only when the problem has the greedy-choice property: a locally optimal choice is always part of some globally optimal solution. Here's a famous failure to build your intuition:

COIN CHANGE — make 6 using coins {1, 3, 4}

  GREEDY (take biggest first):
    6 → take 4 → 2 left → take 1 → take 1   = 3 coins (4+1+1)

  OPTIMAL:
    6 → 3 + 3   = 2 coins  ✗ greedy missed this!

  Greedy FAILS here. The denominations don't have the
  greedy-choice property.

But for "normal" coin systems (like {1, 5, 10, 25}), greedy does give the optimum. The lesson: prove it or test it before trusting greedy.

---

3. Activity Selection (Greedy Works!)

Given activities with start/end times, select the most that don't overlap. Greedy rule: always pick the activity that finishes earliest. This leaves the most room for the rest — and is provably optimal.

function maxActivities(activities) {
    // sort by END time
    activities.sort((a, b) => a.end - b.end);
    let count = 0, lastEnd = -Infinity;
    for (const act of activities) {
        if (act.start >= lastEnd) {     // doesn't overlap
            count++;
            lastEnd = act.end;          // commit, never undo
        }
    }
    return count;
}

HAND TRACE: [(1,3), (2,5), (4,7), (6,8)]  (already sorted by end)
  pick (1,3) → lastEnd=3, count=1
  (2,5): start 2 < 3 → skip (overlaps)
  pick (4,7) → lastEnd=7, count=2
  (6,8): start 6 < 7 → skip
  answer = 2 ✔

---

4. Greedy vs Dynamic Programming

	Greedy	Dynamic Programming
Choice	Best local, commit, never undo	Tries all options, keeps best
Speed	Fast (often O(n log n))	Slower (often O(n·m))
Correctness	Only if greedy-choice holds	Always (explores everything)
Coin change {1,3,4}	Wrong	Correct

RULE OF THUMB:
  Try greedy first — it's simpler. If you can find a
  counterexample, fall back to DP (Chapters 21-22).

---

Interview Questions — Quick Fire!

Q: What is a greedy algorithm?

"One that builds a solution by always taking the locally optimal choice and never reconsidering it. It's fast and simple but only correct when local optima lead to a global optimum — the greedy-choice property."

Q: Give an example where greedy fails.

"Coin change with denominations like {1, 3, 4} making 6: greedy takes 4 then 1 then 1 for three coins, but the optimal is 3 + 3, two coins. The denominations don't satisfy the greedy-choice property, so greedy overshoots."

Q: Why does picking the earliest-finishing activity maximize the count?

"Choosing the activity that ends earliest frees up the most remaining time for future activities, and you can prove by an exchange argument that there's always an optimal solution containing that choice. Sorting by end time then greedily selecting non-overlapping activities is optimal and O(n log n)."

Q: How do you decide between greedy and DP?

"Try greedy first since it's simpler and faster. If you can construct a counterexample where local choices miss the global optimum, the problem lacks the greedy-choice property and you need DP, which explores all options and is always correct."

---

Quick Recap

Concept	Key Takeaway
Greedy idea	Best local choice, commit, never undo.
Works when	Greedy-choice property holds.
Activity selection	Sort by end time → optimal.
Fails	Coin change {1,3,4} making 6.
vs DP	Greedy fast but risky; DP always correct.

What's Next?

Chapter 21: Dynamic Programming (1D) — the most feared topic, made simple. We'll turn that O(2ⁿ) Fibonacci into O(n) and learn to find the recurrence.

Keep coding, keep grinding! See you in the next one!