Greedy Algorithm Learning Roadmap: From Beginner to Interview-Ready in 5 Weeks

You want to master greedy algorithms, but where do you start? How do you know when greedy works vs when you need DP? How do you prove correctness?

This roadmap answers all those questions. It's a structured 5-week learning path that takes you from zero to mastery, with curated problems, rigorous proofs, and a proven progression.

Follow this roadmap, and in 5 weeks, you'll confidently solve any greedy problem—and know exactly when to use DP instead.

How to Use This Roadmap

Time Commitment

• Beginner: 1-2 hours per day, 5 days per week
• Intermediate: 2-3 hours per day, 5 days per week
• Total: 5 weeks to interview-ready

Progression Philosophy

1. Master interval scheduling first (most fundamental pattern)
2. Understand proofs (exchange argument, greedy choice property)
3. Learn when greedy fails (counterexamples)
4. Recognize patterns in 30 seconds
5. Build intuition for greedy vs DP

Milestones

• ✅ Week 1: Solve interval scheduling problems confidently
• ✅ Week 2: Master greedy with sorting and two-pointer patterns
• ✅ Week 3: Understand when greedy works vs when DP is required
• ✅ Week 5: Interview-ready for any greedy problem

Phase 1: Foundations (Weeks 1-2)

Goal: Master the three core greedy patterns.

Week 1: Interval Scheduling

Concepts to Learn:

• What is greedy algorithm?
• Why sort by end time (not start time)
• Greedy choice property
• Exchange argument proof
• When greedy works vs fails

Required Reading:

1. Complete Greedy Algorithm Guide - Read sections 1-3
2. Interval Scheduling Template
3. Why Sort by End Time

Problems to Solve (6 problems):

Practice Template:

# Memorize this template
intervals.sort(key=lambda x: x[1])  # Sort by END time

count = 1
last_end = intervals[0][1]

for start, end in intervals[1:]:
    if start >= last_end:  # No overlap
        count += 1
        last_end = end

return count

Checkpoint: Can you explain why sorting by end time is optimal?

Week 2: Greedy with Sorting and State Tracking

Concepts to Learn:

• Greedy with two-pointer matching
• When to sort both arrays
• Greedy state tracking (maximum reach, cumulative balance)
• Single-pass greedy

Required Reading:

1. Greedy with Sorting Template
2. Greedy State Tracking
3. Assign Cookies Explained

Problems to Solve (7 problems):

Two-Pointer Template:

arr1.sort()
arr2.sort()

i = j = 0
while i < len(arr1) and j < len(arr2):
    if can_match(arr1[i], arr2[j]):
        i += 1
        j += 1
    else:
        j += 1

State Tracking Template:

max_reach = 0

for i in range(len(nums)):
    if i > max_reach:
        return False
    
    max_reach = max(max_reach, i + nums[i])
    
    if max_reach >= len(nums) - 1:
        return True

return True

Checkpoint: Can you solve Jump Game and Gas Station from memory?

Phase 2: Greedy vs DP (Week 3)

Goal: Understand when greedy works vs when DP is required.

Week 3: The Critical Distinction

Concepts to Learn:

• Greedy choice property (when it holds vs fails)
• Classic counterexamples (Coin Change, 0/1 Knapsack)
• Canonical vs non-canonical systems
• Decision framework for greedy vs DP

Required Reading:

1. Greedy vs Dynamic Programming
2. Why Greedy Fails on Coin Change
3. Greedy Choice Property Explained

Problems to Solve (8 problems):

Decision Framework:

1. Can you identify a greedy choice?
   ├─ YES → Continue to step 2
   └─ NO → Use DP

2. Can you find a counterexample?
   ├─ YES (found counterexample) → Use DP
   └─ NO → Continue to step 3

3. Can you prove greedy choice property?
   ├─ YES → Greedy works ✓
   └─ NO → Use DP (safer)

Checkpoint: Can you identify counterexamples where greedy fails?

Phase 3: Proofs and Advanced Techniques (Weeks 4-5)

Goal: Master proof techniques and advanced greedy patterns.

Week 4: Proof Techniques

Concepts to Learn:

• Exchange argument (most powerful technique)
• Greedy choice property proof
• Induction for greedy algorithms
• Optimal substructure

Required Reading:

1. Greedy Proof Techniques
2. Exchange Argument Explained
3. Jump Game: Greedy vs DP
4. Gas Station: Why Greedy Works

Problems to Solve (7 problems):

Exchange Argument Template:

1. Let G = greedy solution, O = optimal solution
2. If G ≠ O, find first difference
3. Exchange element in O with greedy choice
4. Prove exchange maintains optimality
5. Repeat until G = O
6. Conclude: greedy is optimal ✓

Checkpoint: Can you prove interval scheduling correctness using exchange argument?

Week 5: Advanced Techniques and Interview Mastery

Concepts to Learn:

• Two-pass greedy (Candy problem)
• Greedy with priority queue
• Greedy with lookahead (BFS-style)
• Greedy with preprocessing (monotonic stack)

Required Reading:

1. Advanced Greedy Techniques
2. Candy: Two-Pass Greedy
3. Greedy with Priority Queue
4. Wrong Sorting Criterion

Problems to Solve (10 problems):

Two-Pass Greedy Template:

# Pass 1: Left to right
for i in range(1, n):
    if left_constraint(i):
        result[i] = update_left(result, i)

# Pass 2: Right to left (preserve pass 1)
for i in range(n-2, -1, -1):
    if right_constraint(i):
        result[i] = max(result[i], update_right(result, i))

Greedy + Heap Template:

items.sort(key=lambda x: x.criterion)

heap = []
for item in items:
    heapq.heappush(heap, item.value)
    
    if len(heap) > k:
        heapq.heappop(heap)
    
    if len(heap) == k:
        result = optimize(result, heap, item)

Interview Simulation:

• Set 25-minute timer
• Solve problem from scratch
• Explain greedy choice and proof
• Handle "why not DP?" question

Checkpoint: Can you solve any greedy problem in under 20 minutes?

Supplementary Resources

Templates to Memorize

1. Interval Scheduling

intervals.sort(key=lambda x: x[1])
count = 1
last_end = intervals[0][1]

for start, end in intervals[1:]:
    if start >= last_end:
        count += 1
        last_end = end

2. Greedy Two-Pointer

arr1.sort()
arr2.sort()

i = j = 0
while i < len(arr1) and j < len(arr2):
    if can_match(arr1[i], arr2[j]):
        i += 1
        j += 1
    else:
        j += 1

3. Greedy State Tracking

state = initial_value

for i, val in enumerate(arr):
    if not is_reachable(state, i):
        return False
    
    state = update_state(state, val, i)

return is_goal_reached(state)

4. Two-Pass Greedy

# Pass 1: Left to right
for i in range(1, n):
    if condition(i):
        result[i] = update(result, i)

# Pass 2: Right to left
for i in range(n-2, -1, -1):
    if condition(i):
        result[i] = max(result[i], update(result, i))

Common Mistakes Checklist

• Sorting by wrong key (start time instead of end time)
• Not testing with counterexamples
• Using greedy when DP is required
• Wrong comparison operator (> vs >=)
• Not proving greedy choice property
• Forgetting to sort both arrays
• Not handling edge cases (empty input)
• Using one pass when two passes needed

Pattern Recognition Checklist

1. Optimization problem?
   ├─ "Maximize/minimize" → Consider greedy
   └─ "Count all ways" → Not greedy

2. Can identify greedy choice?
   ├─ "Pick earliest-ending" → Interval scheduling
   ├─ "Match smallest-to-smallest" → Greedy sorting
   └─ "Track maximum reach" → State tracking

3. Test with counterexamples
   ├─ Found counterexample → Use DP
   └─ No counterexample → Greedy might work

4. Can prove correctness?
   ├─ Exchange argument works → Greedy ✓
   └─ Can't prove → Use DP (safer)

Progress Tracking

Week-by-Week Checklist

Week 1:

• Read Complete Greedy Guide
• Solve 6 interval scheduling problems
• Memorize interval scheduling template
• Can explain why sort by end time

Week 2:

• Read Greedy Sorting and State Tracking guides
• Solve 7 problems
• Master two-pointer and state tracking templates
• Can solve Jump Game from memory

Week 3:

• Read Greedy vs DP guide
• Solve 8 problems (including Coin Change)
• Understand all classic counterexamples
• Can decide greedy vs DP in 30 seconds

Week 4:

• Read Proof Techniques guides
• Solve 7 problems
• Master exchange argument
• Can prove interval scheduling correctness

Week 5:

• Read Advanced Techniques guides
• Solve 10 advanced problems
• Practice interview simulation
• Interview-ready confidence

Success Metrics

By the end of 5 weeks, you should be able to:

✅ Recognize greedy patterns instantly (< 30 seconds)
✅ Decide greedy vs DP correctly (95%+ accuracy)
✅ Solve easy greedy problems in under 8 minutes
✅ Solve medium greedy problems in under 20 minutes
✅ Prove greedy correctness using exchange argument
✅ Identify counterexamples where greedy fails
✅ Write bug-free greedy code on first attempt (90%+ of the time)

Beyond the Roadmap

After completing this roadmap:

1. Maintain skills - Solve 2-3 greedy problems per week
2. Explore advanced topics - Matroids, greedy on graphs
3. Teach others - Explaining solidifies understanding
4. Apply to real problems - Use in competitive programming
5. Review proofs - Deepen mathematical understanding

Final Tips

Do's

✅ Understand proofs (don't just memorize)
✅ Test with counterexamples
✅ Visualize greedy choices on paper
✅ Practice explaining "why greedy works"
✅ Build intuition for greedy vs DP
✅ Use correct templates consistently

Don'ts

❌ Use greedy without proof
❌ Skip the counterexample articles
❌ Ignore when greedy fails
❌ Confuse greedy with DP
❌ Sort by wrong criterion
❌ Forget to handle edge cases

Conclusion

This roadmap is your structured path to greedy algorithm mastery. Follow it consistently, and in 5 weeks, you'll be interview-ready.

Remember:

• Week 1: Master interval scheduling
• Week 2: Greedy sorting and state tracking
• Week 3: Greedy vs DP distinction
• Week 4: Proof techniques
• Week 5: Advanced techniques and mastery

The journey is systematic, and the reward is confidence. Greedy algorithms are fundamental skills that appear in countless interview problems.

Start with Week 1, Problem #1 (Non-overlapping Intervals #435), and begin your journey to mastery.

Good luck, and happy greedy solving! 🚀

Ready to start? Begin with the Complete Greedy Algorithm Guide and solve your first problem today.