Greedy Algorithms

"Make the best decision now — and trust it leads to the best outcome."

Greedy algorithms are one of the most elegant ideas in computer science. Instead of exploring every possibility, they take a bold approach: at every step, choose the best option available right now.

No backtracking. No reconsideration. Just forward movement.

What is a Greedy Algorithm?

A greedy algorithm builds a solution step by step, always choosing the locally optimal option. The assumption is that these local choices will combine into a globally optimal solution.

Why Greedy Works

Greedy algorithms are powerful because they are:

• Fast — usually O(n log n)
• Simple — easy to implement
• Elegant — minimal logic, maximum efficiency

But greedy is not universal. It only works when the problem satisfies:

• Greedy Choice Property
• Optimal Substructure

Example — Coin Change

Given coins: 25, 10, 5, 1 — make 36 using minimum coins.

Greedy picks largest first:

• 25 → remaining 11
• 10 → remaining 1
• 1 → done

def coin_change(coins, amount):
    coins.sort(reverse=True)
    res = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            res.append(coin)
    return res

Classic Problems

1. Activity Selection

Select maximum number of non-overlapping intervals.

Greedy idea: always pick the activity that ends earliest.

def activity_selection(arr):
    arr.sort(key=lambda x: x[1])
    res = []
    last = -1

    for s, e in arr:
        if s >= last:
            res.append((s, e))
            last = e

    return res

2. Fractional Knapsack

Maximize value with weight constraint. You can take fractions.

Greedy idea: pick highest value/weight ratio first.

def knapsack(items, cap):
    items.sort(key=lambda x: x[0]/x[1], reverse=True)
    total = 0

    for v, w in items:
        if cap >= w:
            total += v
            cap -= w
        else:
            total += v * (cap / w)
            break

    return total

3. Huffman Coding

Used in compression. Merge lowest frequencies first.

import heapq

def huffman(freq):
    heap = [[w, [c, ""]] for c, w in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)

        for p in lo[1:]:
            p[1] = '0' + p[1]
        for p in hi[1:]:
            p[1] = '1' + p[1]

        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])

    return heap

When Greedy Fails

Greedy fails when local choices block better global solutions.

• 0/1 Knapsack → use DP
• Coin Change (non-standard) → DP

Final Thought

Greedy algorithms teach a powerful lesson:

Sometimes, the best strategy is not to overthink — just choose the best option and move forward.