⚡ Greedy Algorithms

🟡 Intermediate Advanced 75 min read

🎯 What are Greedy Algorithms?

A Greedy Algorithm makes the locally optimal choice at each step, hoping to find the global optimum. It never reconsiders past decisions. Greedy algorithms are fast but don't always produce optimal results - you must prove correctness for each problem.

🪙 Real-Life Analogy: Making Change

To make ₹63 with minimum coins [₹50, ₹20, ₹10, ₹2, ₹1]: Pick largest coin ≤ remaining amount. ₹50 → ₹13 left → ₹10 → ₹3 → ₹2 → ₹1 → ₹0. Total: 4 coins. This greedy approach works for standard coin systems!

💡 Classic Greedy Problems

1. Activity Selection (Interval Scheduling)

// Select max number of non-overlapping activities
function activitySelection(array $activities): array {
    // Sort by finish time
    usort($activities, fn($a,$b) => $a['finish'] <=> $b['finish']);

    $selected = [$activities[0]];
    $lastFinish = $activities[0]['finish'];

    for ($i = 1; $i < count($activities); $i++) {
        if ($activities[$i]['start'] >= $lastFinish) {
            $selected[] = $activities[$i];
            $lastFinish = $activities[$i]['finish'];
        }
    }
    return $selected;
}

$acts = [
    ['start'=>1,'finish'=>3],['start'=>2,'finish'=>5],
    ['start'=>4,'finish'=>6],['start'=>6,'finish'=>8]
];
print_r(activitySelection($acts)); // Selects activities ending at 3,6,8
// Time: O(n log n) for sorting, O(n) for selection

2. Fractional Knapsack

function fractionalKnapsack(array $items, float $capacity): float {
    // Sort by value/weight ratio descending
    usort($items, fn($a,$b) => ($b['value']/$b['weight']) <=> ($a['value']/$a['weight']));

    $totalValue = 0;
    foreach ($items as $item) {
        if ($capacity <= 0) break;
        $take = min($item['weight'], $capacity);
        $totalValue += $take * ($item['value'] / $item['weight']);
        $capacity -= $take;
    }
    return $totalValue;
}

$items = [['weight'=>10,'value'=>60],['weight'=>20,'value'=>100],['weight'=>30,'value'=>120]];
echo fractionalKnapsack($items, 50); // 240 (take all of 60 + 100 + 2/3 of 120)
// Note: 0/1 Knapsack requires DP (can't take fractions)

3. Huffman Coding (Data Compression)

// Build Huffman Tree for optimal prefix codes
class HuffmanNode {
    public ?string $char; public int $freq;
    public ?HuffmanNode $left, $right;
    public function __construct(?string $char, int $freq, ?HuffmanNode $l=null, ?HuffmanNode $r=null) {
        $this->char=$char; $this->freq=$freq; $this->left=$l; $this->right=$r;
    }
}

function buildHuffmanTree(array $freq): HuffmanNode {
    $pq = new SplPriorityQueue();
    foreach ($freq as $char => $f) {
        $pq->insert(new HuffmanNode($char, $f), -$f); // min-heap via negative
    }
    while ($pq->count() > 1) {
        $left = $pq->extract(); $right = $pq->extract();
        $pq->insert(new HuffmanNode(null, $left->freq+$right->freq, $left, $right), -($left->freq+$right->freq));
    }
    return $pq->extract();
}

⚙️ When Greedy Works

✅ Optimal Substructure

Optimal solution contains optimal solutions to subproblems.

✅ Greedy Choice Property

Locally optimal choice leads to globally optimal solution.

⚠️ Warning: Greedy does NOT always work! Example: 0/1 Knapsack requires DP. Coin change with [1,3,4] for amount 6: greedy gives 4+1+1=3 coins, optimal is 3+3=2 coins.

📊 Problem Complexity

Activity Selection	O(n log n)	Sorting dominates
Fractional Knapsack	O(n log n)	Sort by ratio
Huffman Coding	O(n log n)	Priority queue operations
Prim's MST	O(E log V)	Priority queue
Kruskal's MST	O(E log E)	Sorting + DSU
Dijkstra	O((V+E)log V)	Priority queue

💼 Interview Questions

Two methods: 1) Greedy Stays Ahead: show greedy never falls behind optimal. 2) Exchange Argument: show any optimal solution can be transformed into greedy solution without losing optimality.

Greedy: one decision, never reconsider. DP: explores multiple options, picks best. If greedy choice property holds, use greedy (faster). Otherwise, use DP. When in doubt, test with counterexamples.

📝 Quick Quiz

Previous: Graph Next: DP