Greedy Algorithms

A greedy algorithm builds a solution step by step, and at each step takes the choice that looks best right now, without ever going back to change it. Greedy algorithms are short and fast, often just "sort, then loop". The catch is that the locally best choice is not always the globally best one, so the real skill is knowing when greedy works.

In this lesson you will solve five problems where greedy is correct, see two where it fails, and learn how to convince yourself (and an interviewer) that a greedy choice is safe.

Scheduling the most events

A college fest in Jaipur has one auditorium and many event requests, each with a start and end time. The organisers want to fit in as many events as possible, with no two overlapping. Which events should they accept?

Three greedy ideas come to mind: pick the shortest events first, pick the earliest-starting events first, or pick the events that finish earliest first. Only the last one always works. Finishing early leaves the most room for everything that comes after.

def schedule(events, key):
    chosen = []
    for name, start, end in sorted(events, key=key):
        if all(end <= s or start >= e for _, s, e in chosen):   # no overlap
            chosen.append((name, start, end))
    return [name for name, _, _ in sorted(chosen, key=lambda c: c[1])]

events = [("Quiz", 9, 12), ("Debate", 10, 11), ("Dance", 11, 13),
          ("Music", 12, 15), ("Drama", 13, 14), ("Coding", 14, 17), ("Prize", 15, 16)]

print("earliest finish:", schedule(events, key=lambda e: e[2]))
print("shortest first: ", schedule(events, key=lambda e: e[2] - e[1]))
print("earliest start: ", schedule(events, key=lambda e: e[1]))

earliest finish: ['Debate', 'Dance', 'Drama', 'Prize']
shortest first:  ['Debate', 'Dance', 'Drama', 'Prize']
earliest start:  ['Quiz', 'Music', 'Prize']

On this input, "shortest first" happens to find 4 too, but "earliest start" only fits 3. Here is the standard clean version of the correct rule, which needs only one comparison per event:

def max_events(events):
    chosen, free_from = [], float("-inf")
    for name, start, end in sorted(events, key=lambda e: e[2]):   # by end time
        if start >= free_from:            # does not overlap the last chosen event
            chosen.append(name)
            free_from = end
    return chosen

events = [("Quiz", 9, 12), ("Debate", 10, 11), ("Dance", 11, 13),
          ("Music", 12, 15), ("Drama", 13, 14), ("Coding", 14, 17), ("Prize", 15, 16)]
print(max_events(events))

# "shortest first" fails here: the short event blocks two longer ones
tricky = [("A", 1, 5), ("B", 4, 7), ("C", 6, 10)]
print(max_events(tricky))

['Debate', 'Dance', 'Drama', 'Prize']
['A', 'C']

In the tricky list, B is the shortest event (3 hours), but taking B blocks both A and C, so "shortest first" would schedule only one event, while "earliest finish" schedules two. Sorting costs O(n log n) and the loop is O(n).

Why earliest finish is safe: take any best schedule. Its first event ends no earlier than the event that finishes first overall. Swap them: the schedule is still valid and still has the same number of events. Repeat for the rest. This exchange argument is the usual way to prove a greedy algorithm correct: show that swapping in the greedy choice never makes an optimal solution worse.

Coin change: when greedy works and when it fails

Giving change with the biggest coin or note first is greedy. With Indian denominations it always gives the fewest pieces, because the denominations are designed that way. With an unusual set it can fail, which is why Dynamic Programming solved the general case.

def greedy_change(denominations, amount):
    pieces = []
    for d in sorted(denominations, reverse=True):
        count, amount = divmod(amount, d)
        pieces += [d] * count
    return pieces if amount == 0 else None

indian = [1, 2, 5, 10, 20, 50, 100, 200, 500]
print(greedy_change(indian, 1288))

tokens = [1, 4, 6]
print(greedy_change(tokens, 8), "but 4 + 4 uses only 2 tokens")

[500, 500, 200, 50, 20, 10, 5, 2, 1]
[6, 1, 1] but 4 + 4 uses only 2 tokens

The lesson: a greedy rule that sounds reasonable is not automatically correct. Try to break it with small counterexamples before you trust it.

Fractional knapsack

In the 0/1 knapsack from Classic DP Problems, each item is taken whole or not at all, and greedy fails. If you may take part of an item, greedy works: take items in order of value per kg, and when the next one does not fit, take the fraction that does.

A dry fruit trader in Srinagar has a 20 kg sack:

stock = [("saffron", 1, 25000), ("almonds", 10, 9000), ("walnuts", 15, 10500),
         ("raisins", 12, 4800), ("apricots", 8, 4000)]        # (name, kg, total Rs)

def fill_sack(stock, capacity):
    plan, total = [], 0.0
    for name, kg, value in sorted(stock, key=lambda s: s[2] / s[1], reverse=True):
        if capacity == 0:
            break
        take = min(kg, capacity)
        plan.append((name, take))
        total += value * take / kg
        capacity -= take
    return plan, total

plan, total = fill_sack(stock, 20)
print(plan)
print(f"Value: Rs {total:,.0f}")

[('saffron', 1), ('almonds', 10), ('walnuts', 9)]
Value: Rs 40,300

The highest value per kg is always worth taking first, because any kg of something cheaper could be swapped for a kg of it without losing value. That exchange argument breaks down in 0/1 knapsack, where you cannot take 9 kg out of a 15 kg item.

Minimum railway platforms

A station master needs to know the minimum number of platforms so that no train ever waits. Process all arrivals and departures in time order: each arrival needs a platform, each departure frees one. The greedy part is reusing the platform that frees up earliest, which a min-heap of departure times does (see Heaps & Priority Queues).

import heapq

trains = [("Shatabdi", 900, 915), ("Intercity", 910, 1100), ("Express", 920, 1000),
          ("Passenger", 1005, 1200), ("Rajdhani", 1015, 1030), ("Mail", 1100, 1130)]

def platforms_needed(trains):
    busy_until = []                                # min-heap of departure times
    most = 0
    for name, arrive, depart in sorted(trains, key=lambda t: t[1]):
        while busy_until and busy_until[0] < arrive:
            heapq.heappop(busy_until)              # that platform is free again
        heapq.heappush(busy_until, depart)
        most = max(most, len(busy_until))
    return most

print(platforms_needed(trains))

3

Times are written as whole numbers like 915 for 9:15, which compare correctly. A train arriving at the exact minute another departs still needs a separate platform here, because of the strict <; whether that is allowed is the kind of detail to clarify in an interview. The running time is O(n log n).

Advanced: Huffman coding

Compression tools store common characters with short bit patterns and rare ones with long patterns. Huffman coding builds the best such code greedily: repeatedly merge the two least frequent groups into one, until one group remains. Each merge adds one bit to the codes of every character inside the two groups.

import heapq
from collections import Counter
from itertools import count

def huffman_codes(text):
    freq = Counter(text)
    tie = count()                                  # breaks ties between equal counts
    heap = [(n, next(tie), {ch: ""}) for ch, n in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        n1, _, left = heapq.heappop(heap)          # the two rarest groups
        n2, _, right = heapq.heappop(heap)
        merged = {ch: "0" + code for ch, code in left.items()}
        merged.update({ch: "1" + code for ch, code in right.items()})
        heapq.heappush(heap, (n1 + n2, next(tie), merged))
    return heap[0][2], freq

text = "mississippi river"
codes, freq = huffman_codes(text)
for ch in sorted(codes, key=lambda c: (len(codes[c]), c)):
    print(repr(ch), freq[ch], codes[ch])
bits = sum(freq[ch] * len(codes[ch]) for ch in freq)
print("Huffman bits:", bits, "| fixed 8-bit:", 8 * len(text))

'i' 5 11
's' 4 00
'p' 2 010
'r' 2 011
' ' 1 1001
'e' 1 1011
'm' 1 1000
'v' 1 1010
Huffman bits: 46 | fixed 8-bit: 136

Frequent letters such as i and s get 2-bit codes; rare ones get 4 bits, and the whole 17-character text needs 46 bits instead of 136. No code is the start of another code (a prefix code), so the bits can be decoded without separators. Huffman's greedy choice is provably optimal among such codes.

Dijkstra's algorithm and Kruskal's algorithm from the graph lessons are greedy too.

Common mistakes

• Trusting a greedy rule without testing it. Look for small counterexamples, or compare with a brute-force solution on random small inputs.
• Sorting by the wrong key, such as start time instead of end time in interval scheduling.
• Using greedy for 0/1 knapsack or arbitrary coin systems. Use DP.
• Ignoring ties and boundaries, such as an event starting exactly when another ends.

Key points

• A greedy algorithm takes the locally best choice at each step and never undoes it.
• It is correct only when the problem has the greedy-choice property; an exchange argument is the usual proof.
• Interval scheduling: sort by finish time and take every event that fits.
• Greedy change works for Indian denominations but not for every coin set; fractional knapsack works by value per kg.
• A min-heap supports greedy choices such as reusing the platform that frees up first and Huffman's merging of the rarest groups.

def cars_needed(weights, limit):
    w = sorted(weights)
    light, heavy = 0, len(w) - 1
    cars = []
    while light <= heavy:
        if light < heavy and w[light] + w[heavy] <= limit:
            cars.append((w[light], w[heavy]))
            light += 1
        else:
            cars.append((w[heavy],))
        heavy -= 1
    return cars

cars = cars_needed([60, 85, 45, 70, 90, 50, 75, 65, 55, 80], 150)
print(len(cars))
print(cars)

5
[(45, 90), (50, 85), (55, 80), (60, 75), (65, 70)]