Greedy Algorithms — Core Concepts

What makes an algorithm greedy

A greedy algorithm builds a solution step by step, making the locally optimal choice at each step. It never reconsiders past choices. This makes greedy algorithms fast — typically O(n log n) due to sorting — but only correct when the problem has two properties:

1. Greedy choice property: A locally optimal choice leads to a globally optimal solution.
2. Optimal substructure: An optimal solution to the problem contains optimal solutions to subproblems.

When both properties hold, greedy gives the correct answer. When they do not, greedy gives an answer that might be wrong.

Classic greedy problems

Activity selection (interval scheduling)

Given a set of activities with start and end times, select the maximum number of non-overlapping activities.

Greedy strategy: Always pick the activity that ends earliest.

def max_activities(activities):
    # Sort by end time
    sorted_acts = sorted(activities, key=lambda x: x[1])
    selected = [sorted_acts[0]]

    for start, end in sorted_acts[1:]:
        if start >= selected[-1][1]:  # no overlap
            selected.append((start, end))

    return selected

# Activities: (start, end)
acts = [(1, 3), (2, 5), (4, 7), (1, 8), (5, 9), (8, 10)]
print(max_activities(acts))
# [(1, 3), (4, 7), (8, 10)] — 3 activities

Why it works: Picking the earliest-finishing activity leaves the most room for future activities. This has been mathematically proven to produce the optimal solution.

Fractional knapsack

You have a knapsack with limited weight capacity. Items have weights and values. You can take fractions of items. Maximize total value.

Greedy strategy: Always take the item with the highest value-per-weight ratio.

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

    for weight, value in sorted_items:
        if capacity >= weight:
            total_value += value
            capacity -= weight
        else:
            total_value += value * (capacity / weight)
            break

    return total_value

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

Important: Greedy works for fractional knapsack but fails for 0/1 knapsack (where you cannot take fractions). The 0/1 version requires dynamic programming.

Coin change (when it works)

With standard US coin denominations (25, 10, 5, 1), greedy gives the minimum number of coins:

def coin_change_greedy(amount, denominations):
    denominations.sort(reverse=True)
    coins_used = []

    for coin in denominations:
        while amount >= coin:
            coins_used.append(coin)
            amount -= coin

    return coins_used

print(coin_change_greedy(63, [25, 10, 5, 1]))
# [25, 25, 10, 1, 1, 1] — 6 coins

This works for US coins because of how the denominations relate to each other. With denominations like [25, 15, 1], greedy fails: it gives 25 + 1×5 = 6 coins for 30¢, when 15 + 15 = 2 coins is better.

How to identify greedy problems

Look for these signals:

• “Maximum number of…” — often interval scheduling
• “Minimum number of…” — often greedy works if the structure is right
• Sorting is the key step — most greedy solutions start with sorting
• The problem has a natural ordering — by deadline, by ratio, by size

Ask yourself: “If I make the locally best choice, can any other choice be better?” If you can argue that the greedy choice never hurts, it is likely correct.

When greedy fails

0/1 Knapsack

You cannot take partial items. Greedy by value-per-weight ratio can give the wrong answer. Use dynamic programming instead.

General coin change

Non-standard denominations break the greedy approach. Use dynamic programming.

Traveling salesman

Always visiting the nearest unvisited city does not give the shortest total tour. This requires more sophisticated algorithms.

Greedy vs dynamic programming

Aspect	Greedy	Dynamic Programming
Decisions	Never revisited	All options considered
Speed	Typically O(n log n)	Often O(n²) or O(n × capacity)
Correctness	Only for specific problems	Always correct if recurrence is right
Implementation	Usually shorter	Usually more complex

When in doubt, start with greedy. If you can prove the greedy choice property holds, you are done. If not, switch to DP.

Common misconception

“Greedy algorithms are simple, so they must be easy.” The algorithms themselves are simple — the hard part is proving they give the correct answer. In interviews, you need to explain why greedy works for the specific problem, not just implement it. A wrong greedy solution that runs fast is still wrong.

One thing to remember: Greedy algorithms are powerful when the problem’s structure guarantees that local optima lead to global optima. Before reaching for the complexity of dynamic programming, always ask: “Does greedy work here?” Often it does, and the solution is dramatically simpler.