2.6 Greedy Algorithms

Deep Dive: When Local Optimal is Global Optimal

Beginner tip: Greedy algorithms are like always taking the largest bill when making change. At each step, you pick whatever looks best RIGHT NOW and never reconsider. This works for some problems (activity scheduling) but fails for others (coin change with weird denominations). The test: can you find a counter-example where greedy gives the wrong answer? If yes, use DP instead.

Jump Game -- Greedy Farthest Reach

nums = [2, 3, 1, 1, 4]. Can you reach the end?

i=0  val=2  farthest = max(0, 0+2) = 2    can reach index 2
i=1  val=3  farthest = max(2, 1+3) = 4    can reach index 4!
i=2  val=1  farthest = max(4, 2+1) = 4    no change
i=3  val=1  farthest = max(4, 3+1) = 4    no change
i=4  reached the end -> TRUE

No backtracking needed. At each index, just track the farthest index reachable. If you ever arrive at an index beyond farthest, you are stuck.

Non-Overlapping Intervals -- Why Sort by END Time

Intervals: [[1,3], [2,4], [3,5], [0,2]]. Maximize non-overlapping count.

Sort by END: [0,2] [1,3] [2,4] [3,5]

Pick [0,2]. end=2.
  [1,3]: starts at 1 < 2 -> OVERLAPS, skip.
  [2,4]: starts at 2 >= 2 -> PICK. end=4.
  [3,5]: starts at 3 < 4 -> OVERLAPS, skip.

Kept 2 intervals. Remove 2 to make non-overlapping.

Why sort by END: Choosing the interval that finishes earliest leaves the MOST room for future intervals. No other choice can do better.

Greedy vs DP -- The Counter-Example Test

Coin Change: coins=[1, 3, 4], amount=6
  Greedy picks: 4, 1, 1 = 3 coins
  DP finds:     3, 3    = 2 coins  -> GREEDY FAILS

Activity Selection: sort by end time
  Always provably optimal -> GREEDY WORKS

Rule: If you cannot prove greedy is optimal, use DP.
      A single counter-example kills greedy.

How to Prove Greedy Is Correct -- The Exchange Argument

Greedy "feels right" is not a proof. The standard tool is the exchange argument:

Assume an optimal solution OPT does not contain the greedy choice g. Show that you can swap g into OPT (replacing some other element) without making the solution worse. Therefore there exists an optimal solution that includes g. Repeat the argument at every step -- the all-greedy solution is also optimal.

Two worked examples.

(a) Jump Game -- "the farthest index reachable so far is always a valid choice."

The greedy claim: while scanning left to right, keep farthest = max(farthest, i + nums[i]); if i ever exceeds farthest, return False. Otherwise return True.

Suppose an optimal jumping strategy OPT reaches the end but at some index i chooses to land somewhere closer than farthest. We can swap that landing point for farthest -- by definition farthest is reachable from i, and from farthest we can reach every index OPT could have reached from a closer landing (because farthest is further along, so it dominates). The swap never makes things worse. Therefore "always extend farthest as much as possible" is optimal.

(b) Merge Intervals -- "sort by start; the earliest-ending overlapping interval is always safe to merge."

The greedy claim: sort intervals by start. Scan left to right. If the current interval overlaps the last merged one, extend its end to max(prev_end, curr_end); otherwise start a new merged group.

Suppose OPT produces a different merged grouping. Pick the first interval where OPT and greedy disagree -- call it X. Greedy merged X into the running group; OPT started a new group with X. But X overlaps the previous interval (that is exactly when greedy merges), so the previous interval and X must live in the same final merged region in any correct answer -- otherwise the output is not a valid merge. Swapping OPT's split for greedy's merge keeps the result valid and uses no more groups. Repeat down the list: greedy is optimal.

The recipe. When you suspect a greedy works:

1. State the greedy choice precisely ("pick the X with the smallest Y").
2. Assume an optimal solution avoids that choice.
3. Construct a swap that puts the greedy choice in without breaking optimality.
4. If you can't construct the swap, you probably have a counter-example -- reach for DP.

---

Quick Reference (Cheat Sheet)

Before You Start -- How to Think About Greedy

What Is Greedy?

Make the locally optimal choice at each step, hoping it leads to the globally optimal solution. No backtracking, no considering alternatives.

When Greedy Works

Greedy works when:
  1. Optimal substructure: optimal solution contains optimal sub-solutions
  2. Greedy choice property: local best -> global best (can you PROVE it?)

Greedy DOESN'T work when:
  - The current best choice can block future better choices
  - You need to consider trade-offs across steps -> Use DP instead

The Greedy Decision

Can I PROVE that the locally best choice never blocks the globally best?
  YES -> Greedy
  NO or UNSURE -> DP or Backtracking

Greedy Problem Archetypes

Type	Strategy	Example
Interval scheduling	Sort by end time, pick non-overlapping	Non-overlapping Intervals
Interval merging	Sort by start time, merge overlapping	Merge Intervals
Jump/reach	Track farthest reachable	Jump Game
Frequency-based	Process most frequent first	Task Scheduler
Partition/split	Track last occurrence	Partition Labels

When You See a Problem, Ask Yourself

1. "Minimum rooms / maximum non-overlapping"? -> Sort by end time (greedy)
2. "Merge overlapping intervals"? -> Sort by start time
3. "Can I reach the end?"/ "Minimum jumps"? -> Track farthest reachable
4. "Schedule with cooldown"? -> Max-frequency first (greedy + heap)
5. "Is greedy correct here?" -> Try a counter-example. If you find one, use DP.

Greedy vs DP Decision

Coin change [1, 3, 4], target = 6:
  Greedy: 4 + 1 + 1 = 3 coins (WRONG)
  DP: 3 + 3 = 2 coins (CORRECT)
  -> Greedy fails because taking 4 blocks the better 3+3 path.

Activity selection (non-overlapping intervals):
  Greedy: always pick shortest-ending activity -> PROVABLY OPTIMAL
  -> Greedy works because early finish leaves max room for future.

Common Mistakes

• Assuming greedy works without proof -- always think of a counter-example
• Sorting by the wrong criterion (start vs end, ascending vs descending)
• Not considering edge cases: empty input, single interval, all overlapping

Problems

#	Problem	Greedy Insight	Status
1	Jump Game	Track farthest reachable	[ ]
2	Jump Game II	BFS / greedy levels	[ ]
3	Gas Station	Net surplus tracking	[ ]
4	Hand of Straights	Sort + group	[ ]
5	Merge Intervals	Sort by start	[ ]
6	Non-overlapping Intervals	Sort by end	[ ]
7	Meeting Rooms II	Sort + heap	[ ]
8	Task Scheduler	Max frequency first	[ ]
9	Partition Labels	Last occurrence	[ ]
10	Valid Parenthesis String	Range tracking	[ ]

Notes