Greedy Algorithms — A Comprehensive Tutorial with Examples, Diagrams & Python Code

What Is a Greedy Algorithm?

A greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most obvious immediate benefit. The key property: no backtracking. Once a choice is made, it stands forever. This makes greedy algorithms blazingly fast — but only correct when the problem has two special properties: greedy choice property and optimal substructure.

When Does Greedy Actually Work?

Greedy is not always correct. It works only when the problem has both of these structural properties. If either is missing, you need dynamic programming or another approach.

How Greedy Works — Step-by-Step Animation

The animation below shows the classic Activity Selection Problem: given a set of activities with start/end times, select the maximum number of non-overlapping activities. Greedy strategy: always pick the activity that finishes earliest.

Activity Selection — Python Implementation

Classic textbook greedy problem. Given n activities with start and finish times, select the maximum number that don't overlap. Greedy strategy: sort by finish time, always pick the next compatible activity.

def activity_selection(activities):
    # activities: list of (start, finish, name) tuples
    # Sort by finish time — the greedy key
    activities = sorted(activities, key=lambda x: x[1])

    selected = []
    last_finish = -1   # track when last selected activity ends

    for start, finish, name in activities:
        if start >= last_finish:   # no overlap → greedy pick
            selected.append(name)
            last_finish = finish

    return selected


# Example: 7 activities
activities = [
    (1, 3, 'A'),
    (2, 5, 'B'),
    (3, 5, 'C'),
    (0, 6, 'D'),
    (5, 7, 'E'),
    (8, 9, 'F'),
    (5, 9, 'G'),
]

result = activity_selection(activities)
print(f"Selected activities: {result}")
print(f"Total selected: {len(result)}")

Coin Change — Where Greedy Works and Where It Doesn't

def coin_change_greedy(coins, amount):
    # Works correctly only for canonical coin systems (e.g. 1,5,10,25)
    coins = sorted(coins, reverse=True)   # largest first
    result = []

    for coin in coins:
        count = amount // coin          # take as many as possible
        result.extend([coin] * count)
        amount -= coin * count

    if amount > 0:
        return None                     # impossible to make change
    return result


# ✓ Works — canonical coins
print(coin_change_greedy([25, 10, 5, 1], 41))

# ✗ Fails — non-canonical: greedy gives 3 coins, DP gives 2
print(coin_change_greedy([4, 3, 1], 6))

Fractional Knapsack — Greedy Shines Here

def fractional_knapsack(capacity, items):
    # items: list of (weight, value) tuples
    # Greedy criterion: sort by value/weight ratio descending
    items = sorted(items, key=lambda x: x[1] / x[0], reverse=True)

    total_value = 0.0
    remaining   = capacity
    breakdown   = []

    for weight, value in items:
        if remaining <= 0:
            break
        take       = min(weight, remaining)   # take whole or fraction
        fraction   = take / weight
        gained     = value * fraction
        total_value += gained
        remaining  -= take
        breakdown.append((weight, value, round(fraction, 2), round(gained, 2)))

    return round(total_value, 2), breakdown


# Items: (weight_kg, value_₹)
items    = [(10, 60), (20, 100), (30, 120)]
capacity = 50

total, bd = fractional_knapsack(capacity, items)
print(f"Max value: ₹{total}")
for w, v, frac, gain in bd:
    print(f"  Item({w}kg,₹{v}) — ratio={v/w:.1f} — took {frac*100:.0f}% → ₹{gain}")

Huffman Coding — Greedy Data Compression

import heapq
from collections import Counter

class Node:
    def __init__(self, char, freq):
        self.char  = char
        self.freq  = freq
        self.left  = None
        self.right = None
    def __lt__(self, other):
        return self.freq < other.freq   # min-heap by frequency


def huffman_codes(text):
    freq = Counter(text)
    heap = [Node(c, f) for c, f in freq.items()]
    heapq.heapify(heap)

    # Greedy: always merge the two LEAST frequent nodes
    while len(heap) > 1:
        left  = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = Node(None, left.freq + right.freq)
        merged.left, merged.right = left, right
        heapq.heappush(heap, merged)

    # Walk tree to extract codes
    codes = {}
    def walk(node, code=''):
        if node.char:
            codes[node.char] = code or '0'
        else:
            walk(node.left,  code + '0')
            walk(node.right, code + '1')
    walk(heap[0])
    return codes, freq


text = "greedy algorithms are amazingly efficient"
codes, freq = huffman_codes(text)

original_bits  = len(text) * 8
compressed_bits = sum(freq[c] * len(codes[c]) for c in codes)

print(f"Original : {original_bits} bits (8 bits/char fixed)")
print(f"Huffman  : {compressed_bits} bits")
print(f"Saved    : {100*(1 - compressed_bits/original_bits):.1f}%")
print()
for c in sorted(codes, key=lambda x: freq[x], reverse=True)[:6]:
    print(f"  '{c}' freq={freq[c]}  code={codes[c]}")

Dijkstra's Algorithm — Greedy Shortest Path

import heapq

def dijkstra(graph, start):
    # graph: {node: [(neighbour, weight), ...]}
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    prev = {node: None for node in graph}
    pq   = [(0, start)]   # (distance, node) min-heap

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue   # stale entry, skip

        for v, weight in graph[u]:
            # Greedy relaxation: is this path shorter?
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                prev[v] = u
                heapq.heappush(pq, (dist[v], v))

    return dist, prev


def reconstruct_path(prev, target):
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = prev[node]
    return path[::-1]


graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 5), ('C', 1)],
    'C': [('B', 1), ('D', 8), ('E', 10)],
    'D': [('E', 2), ('F', 6)],
    'E': [('F', 3)],
    'F': [],
}

dist, prev = dijkstra(graph, 'A')
path = reconstruct_path(prev, 'F')

for node, d in dist.items():
    print(f"  A → {node} : {d}")
print(f"\nShortest path A→F: {' → '.join(path)} (cost {dist['F']})")

Greedy Algorithms — Time Complexity Reference

Interval Colouring — Meeting Rooms Problem

import heapq

def min_meeting_rooms(intervals):
    if not intervals:
        return 0

    # Sort meetings by start time
    intervals = sorted(intervals, key=lambda x: x[0])
    # Min-heap stores end times of active rooms
    end_times = []

    for start, end in intervals:
        if end_times and end_times[0] <= start:
            # Reuse earliest-finishing room
            heapq.heapreplace(end_times, end)
        else:
            # No room free — open a new one
            heapq.heappush(end_times, end)

    return len(end_times)


meetings = [(0,30),(5,10),(15,20),(7,15),(20,25)]
print(f"Min rooms needed: {min_meeting_rooms(meetings)}")

Greedy vs Dynamic Programming — The Definitive Comparison

Job Sequencing with Deadlines — Profit Maximisation

Given n jobs, each with a deadline and profit (earned only if completed by deadline), and one machine that handles one job at a time (each job takes one unit of time) — maximise total profit. Greedy strategy: sort by profit descending, schedule each job in the latest available slot before its deadline.

def job_sequencing(jobs):
    # jobs: list of (job_id, deadline, profit)
    jobs = sorted(jobs, key=lambda x: -x[2])  # sort by profit desc
    max_deadline = max(d for _, d, _ in jobs)
    slots = [None] * (max_deadline + 1)   # slots[0] unused

    total_profit = 0
    scheduled   = []

    for job_id, deadline, profit in jobs:
        # Find latest free slot ≤ deadline
        for slot in range(min(deadline, max_deadline), 0, -1):
            if slots[slot] is None:
                slots[slot] = job_id
                total_profit += profit
                scheduled.append(job_id)
                break

    return scheduled, total_profit


jobs = [
    ('J1', 2, 100),
    ('J2', 1, 19),
    ('J3', 2, 27),
    ('J4', 1, 25),
    ('J5', 3, 15),
]

sched, profit = job_sequencing(jobs)
print(f"Scheduled: {sched}")
print(f"Total Profit: ₹{profit}")

The 6 Golden Rules of Greedy Algorithms