Greedy Algorithms

📋 At a Glance

┌─────────────────────────────────────────────────────────────────┐
│                    GREEDY ALGORITHMS                            │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  THE GREEDY APPROACH                                            │
│  ┌─────────────────────────────────────────────────────────┐    │
│  │                                                         │    │
│  │  At each step, make the locally optimal choice          │    │
│  │  Hope it leads to globally optimal solution             │    │
│  │                                                         │    │
│  │  ┌─────┐    ┌─────┐    ┌─────┐    ┌─────┐               │    │
│  │  │Start│───→│Best │───→│Best │───→│Goal │               │    │
│  │  │     │    │local│    │local│    │     │               │    │
│  │  └─────┘    └─────┘    └─────┘    └─────┘               │    │
│  │                                                         │    │
│  │Works when: Greedy choice property + Optimal substructure│    │
│  │                                                         │    │
│  └─────────────────────────────────────────────────────────┘    │
│                                                                 │
│  CLASSIC PROBLEMS                                               │
│  ┌─────────────────┐  ┌─────────────────┐                       │
│  │ Activity Select │  │ Huffman Coding  │                       │
│  │ ─────────────── │  │ ─────────────── │                       │
│  │ Max activities  │  │ Optimal prefix  │                       │
│  │ without overlap │  │ codes           │                       │
│  └─────────────────┘  └─────────────────┘                       │
│                                                                 │
│  ┌─────────────────┐  ┌─────────────────┐                       │
│  │ Fractional      │  │ Job Scheduling  │                       │
│  │ Knapsack        │  │ ─────────────── │                       │
│  │ ─────────────── │  │ Minimize        │                       │
│  │ Max value with  │  │ penalties       │                       │
│  │ fractions       │  │                 │                       │
│  └─────────────────┘  └─────────────────┘                       │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

🎯 What You'll Learn

After completing this article, you will be able to:

1. Identify greedy problems: Recognize when greedy works
2. Prove correctness: Exchange argument and greedy stays ahead
3. Solve classic problems: Activity selection, Huffman, scheduling
4. Avoid pitfalls: Know when greedy fails

🔥 Production Story: The Task Scheduler Optimization

A cloud platform needed to schedule thousands of tasks to minimize total completion time.

The Problem

JAVA(10 lines)
Code
Loading syntax highlighter...

The Solution: Shortest Job First

JAVA(30 lines)
Code
Loading syntax highlighter...

Why It Works (Exchange Argument)

If tasks aren't in SJF order, we can improve by swapping adjacent jobs:

Before swap: [..., A, B, ...]  where duration(A) > duration(B)
            A completes at time t
            B completes at time t + duration(B)

After swap:  [..., B, A, ...]
            B completes at time t - duration(A) + duration(B) = t'
            A completes at time t

Since duration(B) < duration(A):
- B's completion time decreased
- A's completion time stayed same
- Total improved!

Therefore, SJF order is optimal.

🧠 Mental Model: The Greedy Framework

┌─────────────────────────────────────────────────────────────────┐
│                 GREEDY ALGORITHM FRAMEWORK                      │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  STEP 1: Identify the greedy choice                             │
│  ┌─────────────────────────────────────────────────────────┐    │
│  │ What's the "best" item to pick first?                   │    │
│  │ - Largest? Smallest? Earliest finish? Best ratio?       │    │
│  └─────────────────────────────────────────────────────────┘    │
│                                                                 │
│  STEP 2: Prove greedy choice is safe                            │
│  ┌─────────────────────────────────────────────────────────┐    │
│  │ Show: There exists an optimal solution that includes    │    │
│  │       our greedy choice                                 │    │
│  │                                                         │    │
│  │ Methods:                                                │    │
│  │ - Exchange argument                                     │    │
│  │ - Greedy stays ahead                                    │    │
│  │ - Structural argument                                   │    │
│  └─────────────────────────────────────────────────────────┘    │
│                                                                 │
│  STEP 3: Prove optimal substructure                             │
│  ┌─────────────────────────────────────────────────────────┐    │
│  │ After making greedy choice, remaining problem is        │    │
│  │ smaller instance of same problem                        │    │
│  └─────────────────────────────────────────────────────────┘    │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

🔬 Deep Dive: Activity Selection

The Problem

Given activities with start and end times, select maximum non-overlapping activities.

JAVA(18 lines)
Code
Loading syntax highlighter...

Why Earliest Finish First Works

┌─────────────────────────────────────────────────────────────────┐
│            ACTIVITY SELECTION PROOF                             │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Claim: Greedy choice (earliest finish) is always safe          │
│                                                                 │
│  Proof by exchange:                                             │
│  Let OPT be any optimal solution                                │
│  Let a₁ be the activity with earliest finish time               │
│  Let a_first be the first activity in OPT                       │
│                                                                 │
│  If a₁ = a_first: Done! Greedy matches OPT                      │
│                                                                 │
│  If a₁ ≠ a_first:                                               │
│    - a₁ finishes no later than a_first (earliest finish)        │
│    - Replace a_first with a₁ in OPT                             │
│    - No new conflicts (a₁ ends earlier)                         │
│    - Same size, still valid → OPT' is optimal with a₁           │
│                                                                 │
│  Timeline:                                                      │
│  a₁:     |-----|                                                │
│  a_first:|--------|                                             │
│  next:            |-----|                                       │
│                                                                 │
│  Swapping a_first → a₁ can only add more room for next          │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Weighted Activity Selection

When activities have weights, greedy doesn't work - need DP:

JAVA(35 lines)
Code
Loading syntax highlighter...

🔬 Deep Dive: Huffman Coding

The Problem

Create optimal prefix-free codes for data compression.

┌─────────────────────────────────────────────────────────────────┐
│                    HUFFMAN CODING                               │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Characters: a(45%), b(13%), c(12%), d(16%), e(9%), f(5%)       │
│                                                                 │
│  Fixed-length: 3 bits each → 3 × 100 = 300 bits                 │
│                                                                 │
│  Huffman tree:                                                  │
│              (100)                                              │
│             /     \                                             │
│          (55)     a(45)                                         │
│         /    \       0                                          │
│      (25)    (30)                                               │
│      /  \    /  \                                               │
│    c(12) b(13) d(16) (14)                                       │
│     100   101   110  /  \                                       │
│                    f(5) e(9)                                    │
│                    1110  1111                                   │
│                                                                 │
│  Huffman: 1×45 + 3×13 + 3×12 + 3×16 + 4×9 + 4×5 = 224 bits      │
│  Savings: 25%                                                   │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Implementation

JAVA(87 lines)
Code
Loading syntax highlighter...
Show all 87 lines

Why Huffman is Optimal

Greedy choice: Always merge two nodes with smallest frequencies

Proof idea:
1. Optimal tree exists where two lowest-frequency symbols are siblings
   at the deepest level (exchange argument)

2. After merging, we have smaller instance of same problem
   (one fewer symbol, combined frequency)

3. Recursively optimal → globally optimal

🔬 Deep Dive: Fractional Knapsack

The Problem

Unlike 0/1 knapsack, we can take fractions of items.

JAVA(36 lines)
Code
Loading syntax highlighter...

Comparison with 0/1 Knapsack

Items: weights = [10, 20, 30], values = [60, 100, 120], capacity = 50

Ratios: 60/10=6, 100/20=5, 120/30=4

Fractional (greedy):
- Take all of item 1: value=60, remaining=40
- Take all of item 2: value=60+100=160, remaining=20
- Take 20/30 of item 3: value=160+120×(20/30)=240

0/1 (DP needed):
- Take items 2 and 3: value=100+120=220

Greedy gives 240 for fractional, but would give wrong answer for 0/1!

🔬 Deep Dive: Job Scheduling

Minimizing Lateness

JAVA(24 lines)
Code
Loading syntax highlighter...

Job Scheduling with Profits and Deadlines

JAVA(71 lines)
Code
Loading syntax highlighter...
Show all 71 lines

🔬 Deep Dive: When Greedy Fails

Coin Change Problem

JAVA(19 lines)
Code
Loading syntax highlighter...

The Key Difference

┌─────────────────────────────────────────────────────────────────┐
│           GREEDY vs DYNAMIC PROGRAMMING                         │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  GREEDY                                                         │
│  ───────                                                        │
│  - Makes one choice at each step                                │
│  - Never reconsiders choices                                    │
│  - Works when: greedy choice property holds                     │
│  - Time: Usually O(n) or O(n log n)                             │
│                                                                 │
│  DYNAMIC PROGRAMMING                                            │
│  ────────────────────                                           │
│  - Considers all choices at each step                           │
│  - Stores results for future use                                │
│  - Works when: optimal substructure only                        │
│  - Time: Usually O(n²) or O(n×k)                                │
│                                                                 │
│  Rule of thumb:                                                 │
│  ───────────────                                                │
│  1. Try greedy first (simpler, faster)                          │
│  2. Find counterexample → use DP                                │
│  3. Prove greedy works → keep greedy                            │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

⚠️ Common Mistakes

Mistake 1: Assuming Greedy Always Works

JAVA(10 lines)
Code
Loading syntax highlighter...

Mistake 2: Wrong Greedy Criterion

JAVA(5 lines)
Code
Loading syntax highlighter...

Mistake 3: Not Handling Ties Properly

JAVA(16 lines)
Code
Loading syntax highlighter...

🐛 Debug This: Activity Selection Bug

This activity selection has a bug. Can you find it?

JAVA(16 lines)
Code
Loading syntax highlighter...

JAVA(5 lines)
Code
Loading syntax highlighter...

Activities: [0,10], [1,3], [3,5], [5,7], [7,9]

Shortest duration first: [1,3] (len 2), [3,5] (len 2), [5,7] (len 2), [7,9] (len 2), [0,10] (len 10)
Result: [1,3], [3,5], [5,7], [7,9] = 4 activities ✓

But consider: [0,2], [1,10], [2,3]
Shortest first: [0,2] (len 2), [2,3] (len 1), [1,10] (len 9)
Order: [2,3], [0,2], [1,10]
Result: [2,3] (can't add [0,2] - overlaps!) = 1 activity

Earliest finish: [0,2], [2,3], [1,10]
Result: [0,2], [2,3] = 2 activities ✓

💻 Exercises

Exercise 1: Assign Mice to Holes ⭐⭐

N mice and N holes on a line. Find minimum time for all mice to reach holes (each mouse to one hole).

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 2: Minimum Platforms ⭐⭐

Given arrival and departure times of trains, find minimum platforms needed.

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 3: Gas Station ⭐⭐⭐

N gas stations in a circle. Find starting station to complete the circuit.

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 4: Jump Game II ⭐⭐⭐

Minimum jumps to reach end. Each position has max jump length.

JAVA(3 lines)
Code
Loading syntax highlighter...

Exercise 5: Meeting Rooms III ⭐⭐⭐⭐

Given n rooms and meetings, find which room held most meetings. Meetings go to lowest numbered available room.

JAVA(3 lines)
Code
Loading syntax highlighter...

🎤 Interview Questions

Q1: "How do you prove a greedy algorithm is correct?"

• Take any optimal solution OPT
• Show we can transform it to match greedy without worsening
• Usually swap elements to show greedy choice is at least as good

• Define a measure of progress
• Show greedy solution is always at least as good as any other
• By induction: if greedy is ahead at step k, it stays ahead at step k+1

Exchange: If OPT's first activity isn't earliest-finish,
          swap it with earliest-finish activity.
          Result: same or fewer conflicts.

Stays ahead: At each step, greedy has at least as many
             activities AND ends no later than any other
             solution with same number of activities.

Q2: "When should I try greedy vs DP?"

• Problem has "optimal substructure"
• Local choices seem to lead to global optimum
• You can identify a clear greedy criterion

• Greedy counterexample exists
• Need to consider multiple choices
• Problem has overlapping subproblems

1. Propose greedy strategy
2. Try to find counterexample
3. If found → use DP
4. If not → try to prove greedy works

Q3: "Implement interval scheduling with weights."

JAVA(30 lines)
Code
Loading syntax highlighter...

Key insight: Greedy doesn't work with weights. Need DP because taking an interval affects which others we can take.

Q4: "Design an algorithm for task scheduling with dependencies."

JAVA(32 lines)
Code
Loading syntax highlighter...

Q5: "What's the difference between Huffman and Shannon-Fano coding?"

1. Merging two smallest frequencies is provably safe
2. Resulting tree has minimum weighted path length

Shannon-Fano can produce suboptimal codes because splitting by frequency doesn't guarantee optimal bit allocation.

📋 Quick Reference

Classic Greedy Problems

When Greedy Fails

Proof Techniques

Exchange Argument:
1. Let OPT be optimal solution
2. If OPT differs from greedy at step k
3. Show we can swap to match greedy
4. Solution doesn't worsen → greedy is optimal

Greedy Stays Ahead:
1. Define measure M (e.g., activities selected)
2. Show M(greedy, k) ≥ M(any other, k) for all k
3. By induction, greedy ends up optimal

🔗 What's Next?

• Backtracking template
• N-Queens, Sudoku solver
• Subset/permutation generation
• Branch and bound optimization

📅 Review Schedule