roadmap/Greedy

Topic 12 / 16

Greedy

HardOptimization~4 days
Challenging
progress0 / 10 solved

Make the locally optimal choice at each step. Prove it leads to a global optimum.

⚠️
Why this topic is hard

Greedy is hard because it looks deceptively simple — just make the locally best choice. The real challenge is PROVING the greedy choice is safe. Many problems look greedy but actually need DP. The test: if making a greedy choice at step i could ever force you into a worse outcome at step j, greedy fails and you need DP.

Concept

At each step, make the choice that looks best right now without reconsidering past choices. Greedy works when local optima lead to a global optimum — this is usually provable by an exchange argument. If greedy fails, fall back to DP.

When to use this pattern
  • ◆Activity selection / interval scheduling
  • ◆Minimum number of items to cover a range
  • ◆Jump game (can you reach the end?)
  • ◆Huffman encoding
  • ◆Gas station circular tour
Common patterns
Sort then sweep
Sort by start or end time; make greedy decisions in order.
Reach maximization
Track the farthest reachable index; update at each step.
Priority-based
Always pick the next best option using a heap.
Brute force → optimal thinking
Brute force
Try all possible sequences of choices → exponential.
Observation
Identify the greedy choice property: making the locally best choice doesn't prevent reaching the global optimum.
Optimization
Sort the input by the relevant criterion. Sweep through making greedy choices.
Final complexity
O(n log n) due to sorting, then O(n) sweep.
Quick Recall Check

What must you prove for a greedy algorithm to be correct?

In Jump Game, what do you track to determine if the end is reachable?

When does greedy fail and DP become necessary?

Am I ready to move on?

Check each question you can answer confidently before moving to the next topic.

←
previous
Dynamic Programming
next
Intervals
→
Progress is saved on this device