Greedy Algorithm

In Turkish: Açgözlü Algoritma

Updated September 30, 20263 min read

In short

A greedy algorithm builds a solution step by step, always taking the choice that looks best right now, without going back to reconsider earlier decisions.

What is a greedy algorithm?

A greedy algorithm solves a problem through a series of choices, and at each step it picks whatever option looks best at that moment, called the locally optimal choice. It never revisits a decision once it has been made. This makes greedy algorithms simple to write and usually very fast, but they only find the best overall answer for problems with the right structure.

A greedy approach is guaranteed to work when a problem has two properties: the greedy choice property, meaning a locally best choice can always be part of some optimal solution, and optimal substructure, meaning what remains after that choice is a smaller version of the same problem. Proving the first property is the hard part, and it is often done with an exchange argument, which shows that any optimal solution can be changed to include the greedy choice without getting worse. Many greedy algorithms start by sorting their input, so they commonly run in O(n log n) time.

Making change with as few coins as possible is the classic example: with coins of 25, 10, 5, and 1 cents, always handing over the largest coin that fits gives the best answer. Well-known greedy algorithms include Dijkstra's shortest-path algorithm, Prim's and Kruskal's algorithms for minimum spanning trees, Huffman coding for data compression, and interval scheduling, which fits the most meetings into one room by always picking the one that ends earliest. When a problem is too hard to solve exactly, greedy methods also serve as fast heuristics that give a good, though not always the best, answer.

Greedy algorithms are often confused with dynamic programming, since both work on problems with optimal substructure. A greedy algorithm commits to one choice at each step, while dynamic programming considers every choice and combines the stored results of subproblems, which is slower but correct in cases where greed fails. The coin example shows the difference: with coins of 1, 3, and 4, making 6 greedily gives 4 + 1 + 1, three coins, while dynamic programming finds 3 + 3, just two.

Key takeaways

A greedy algorithm always takes the choice that looks best right now and never backtracks.
It is optimal only when the problem has the greedy choice property and optimal substructure.
Examples include Dijkstra's algorithm, Huffman coding, and Kruskal's and Prim's minimum spanning tree algorithms.
Greedy algorithms are usually fast, often O(n log n) because they sort the input first.
Dynamic programming considers all choices, so it solves problems where greedy choices fail.

Example

Greedy interval scheduling: fit the most meetings into one roompython

def max_meetings(meetings):
    # Greedy choice: always take the meeting that ends earliest
    chosen, free_at = [], 0
    for start, end in sorted(meetings, key=lambda m: m[1]):  # O(n log n)
        if start >= free_at:  # it fits after the last chosen meeting
            chosen.append((start, end))
            free_at = end
    return chosen

meetings = [(9, 12), (9, 10), (10, 11), (11, 13), (12, 14), (13, 15)]
print(max_meetings(meetings))  # [(9, 10), (10, 11), (11, 13), (13, 15)]

Readers ask

When does a greedy algorithm give the optimal answer?

When the problem has the greedy choice property, so a locally best choice never rules out the best overall solution, and optimal substructure. Interval scheduling, minimum spanning trees, and Huffman coding are proven cases, while for many other problems greedy gives only an approximation.

What is the difference between a greedy algorithm and dynamic programming?

A greedy algorithm makes one irreversible choice per step based on what looks best now. Dynamic programming evaluates all choices using stored answers to subproblems, which costs more time and memory but finds the optimum where greedy choices fail.

Is Dijkstra's algorithm greedy?

Yes. At each step it finalizes the unvisited node with the smallest known distance, which is a greedy choice, and this is provably correct as long as no edge weights are negative.