Greedy algorithms explained: how they work, code and examples

What problem greedy algorithms solve

Greedy algorithms target optimization problems: choose the most activities, use the fewest coins, build the cheapest network, compress a file into the fewest bits. Instead of exploring every combination, a greedy algorithm sorts or prioritizes the options and commits to the best one at each step. That usually gives O(n log n) time, often just the cost of sorting.

The hard part is not the code but the proof. Many natural greedy rules are wrong, so you must either prove that the rule is correct or test it against a brute-force solution.

The idea in plain words

1. Find a rule that ranks the choices, for example "earliest finishing time first" or "lightest edge first".
2. Sort the options by that rule, or keep them in a priority queue.
3. Go through the options and take each one that is still allowed by the constraints.
4. Never undo a choice.

A greedy algorithm is correct when two properties hold. Greedy-choice property: some optimal solution contains the first greedy choice. Optimal substructure: after making that choice, the rest of the problem is a smaller instance of the same problem. The usual proof is an exchange argument: take any optimal solution and show that swapping one of its choices for the greedy choice does not make it worse.

Worked example: interval scheduling

You have one meeting room and these requests (start, end): A (1, 4), B (3, 5), C (0, 6), D (5, 7), E (3, 9), F (5, 9), G (6, 10), H (8, 11). Book as many non-overlapping meetings as possible. The correct greedy rule is: always pick the meeting that ends first among those that start after the last booked one ends.

Result: A, D, H, three meetings, which is the maximum. Why it works: the meeting that ends first leaves the most time for everything else, so replacing the first meeting of any optimal schedule with it never causes a conflict.

Python implementation

def max_meetings(meetings):
    """meetings: list of (name, start, end). Returns the booked names."""
    booked, last_end = [], float("-inf")
    for name, start, end in sorted(meetings, key=lambda m: m[2]):
        if start >= last_end:
            booked.append(name)
            last_end = end
    return booked

requests = [("A", 1, 4), ("B", 3, 5), ("C", 0, 6), ("D", 5, 7),
            ("E", 3, 9), ("F", 5, 9), ("G", 6, 10), ("H", 8, 11)]
print(max_meetings(requests))  # ['A', 'D', 'H']

A second classic example is the fractional knapsack: when you may take part of an item, taking items in order of value per unit of weight is optimal.

def fractional_knapsack(items, capacity):
    """items: list of (value, weight). Returns the best total value."""
    total = 0.0
    for value, weight in sorted(items, key=lambda i: i[0] / i[1], reverse=True):
        take = min(weight, capacity)
        total += value * take / weight
        capacity -= take
        if capacity == 0:
            break
    return total

print(fractional_knapsack([(60, 10), (100, 20), (120, 30)], 50))  # 240.0

When greedy fails: counterexamples

Time and space complexity

Space is usually O(n) for the sorted copy or the heap. If the input is already sorted, many greedy algorithms run in O(n).

When to use greedy and real-world uses

• Use greedy when you can prove the greedy-choice property, or when a fast approximate answer is acceptable. Otherwise use dynamic programming or backtracking.
• Compression: Huffman coding builds optimal prefix codes by repeatedly merging the two least frequent symbols; it is used inside formats such as DEFLATE (ZIP, gzip, PNG).
• Networks: minimum spanning trees (Kruskal, Prim) and shortest path routing (Dijkstra).
• Scheduling: earliest deadline first, and booking rooms or machines.
• Approximation: for set cover, the greedy rule "pick the set covering the most uncovered items" is not optimal but is guaranteed to be within a logarithmic factor of the optimum.
• Interview problems: jump game, gas station, assign cookies, non-overlapping intervals, minimum number of arrows to burst balloons, task scheduler.