A greedy algorithm builds a solution one step at a time, picking whichever option looks best at that moment. Once a choice is made, it is never reconsidered.

This works well when local choices add up to a globally optimal answer. It fails when an early choice that looks good blocks a better path later on.

The key characteristics of greedy algorithms:

The greedy path (solid arrows) commits to choices without exploring alternatives (dotted arrows). This is both its strength (efficiency) and its weakness (may miss better solutions).

Greedy algorithms work when the problem has two key properties:

1. Greedy Choice Property

A globally optimal solution can be constructed by making locally optimal choices. In other words, choosing what looks best right now will not prevent us from finding the best overall solution.

For the coin change example with US denominations (25, 10, 5, 1 cents), always picking the largest coin that fits gives the minimum number of coins. But this is not universally true. If coins were (1, 3, 4) cents and we needed 6 cents, greedy would pick 4 + 1 + 1 = 3 coins, but 3 + 3 = 2 coins is optimal.

2. Optimal Substructure

An optimal solution to the problem contains optimal solutions to its subproblems. After making a greedy choice, the remaining problem should also have an optimal solution that, combined with the greedy choice, gives the overall optimum.

Consider activity selection: if we greedily pick an activity that ends earliest, the remaining problem is to select activities from those that start after this one ends. The optimal solution to this subproblem, combined with our greedy choice, gives the global optimum.

Greedy is for optimization problems (max/min). For counting problems (how many ways) or feasibility-with-many-solutions, greedy typically does not apply.

Greedy as an Approximation Tool

Even when greedy does not produce the exact optimum, it often produces a solution with a provable approximation guarantee. For set cover, the greedy strategy of repeatedly picking the set that covers the most uncovered elements gives an O(log n) approximation, and no polynomial algorithm is known to do better. For vertex cover, a simple greedy that picks both endpoints of any uncovered edge gives a 2-approximation. Greedy is also the standard tool for makespan-minimization scheduling, where list scheduling achieves a (2 - 1/m) approximation on m machines. In competitive programming interviews this angle is less common, but greedy is not a binary "works or fails" tool. It often gives the best known polynomial-time answer when the exact problem is NP-hard.

A greedy algorithm is only as trustworthy as the proof behind it. The exchange argument is the main technique for showing that local choices produce a global optimum.

The Setup

Suppose the greedy algorithm produces a solution G. The goal is to prove that G is optimal. The strategy:

Each modification preserves optimality, so the end result, which equals G, is also optimal.

Two Patterns

Exchange argument (swap): Identify the differing element in O. Swap it with the greedy choice. Prove the swap does not decrease the value for maximization problems, or does not increase the cost for minimization problems. Repeat until O matches G.

Greedy-stays-ahead: Show that after step i, the greedy partial solution is at least as good as any optimal partial solution of the same size. Since this holds at every step, the final greedy solution is at least as good as the final optimal solution.

The two patterns often work for the same problem. Greedy-stays-ahead tends to be cleaner when the algorithm builds the solution one element at a time and "as good as" can be measured numerically. The swap version is more flexible when the structure of the solution is what matters, not just a single number.

Worked Example: Activity Selection

Given activities with start and end times, the goal is to select the maximum number of non-overlapping activities. The greedy algorithm sorts by end time, picks the activity that ends earliest, then repeatedly picks the next activity that starts after the previous one's end.

Let G = [g_1, g_2, ..., g_k] be the greedy schedule, sorted by selection order (which is also sorted by end time). Let O = [o_1, o_2, ..., o_m] be any optimal schedule, sorted by start time. The goal is to prove k = m.

Step 1: The first activity. Greedy picks the activity with the earliest end time, so end(g_1) <= end(o_1).

Step 2: The swap. Replace o_1 with g_1 in O. The resulting schedule O' = [g_1, o_2, ..., o_m] is still valid:

O' has the same size m and is still optimal.

Step 3: Induction. Apply the same argument at position 2. The greedy algorithm now picks g_2, the earliest-ending activity among those that start after end(g_1). Since o_2 in O' also starts after end(g_1) and is a valid choice, end(g_2) <= end(o_2). Swap o_2 with g_2. By the same reasoning, o_3 remains compatible and the schedule stays valid.

Continue swapping for each position. After k swaps, the first k positions of O' equal G. Since G has no more activities to add (greedy stopped), no activity in O' beyond position k can start after end(g_k) and still be valid, which forces m <= k.

The reverse inequality k <= m holds because G is a valid schedule and O is optimal. Together, k = m. Greedy is optimal.

The same template, swap the first differing element and show the swap preserves validity and value, works for interval scheduling variants, Huffman coding, scheduling to minimize lateness, and many other classic greedy problems.

Here is how the three techniques compare:

How to identify which to use:

One workable approach is to propose greedy first, look for a counterexample where it fails, and switch to DP if one exists.

Certain problem types have well-known greedy solutions.

Pattern 1: Interval Scheduling

Problem type: Select maximum non-overlapping intervals, or minimum intervals to cover a range.

Greedy strategy: Sort by end time and pick intervals that end earliest.

Picking the interval that ends earliest leaves the most room for the intervals that follow.

Problems using this pattern:

Pattern 2: Greedy Scheduling

Problem type: Minimize total wait time or maximize throughput.

Greedy strategy: Process shortest jobs first (SJF) or prioritize by some efficiency metric.

Finishing short tasks first cuts down the time every later task spends waiting.

Problems using this pattern:

Pattern 3: Two-Pointer Greedy

Problem type: Problems involving sorted arrays where you need to find pairs or optimize based on positions.

Greedy strategy: Use two pointers (often start and end) and greedily move the pointer that improves the solution.

Moving the "less promising" pointer cannot miss a better solution, since any pair involving it is already bounded by the other pointer.

Problems using this pattern:

Pattern 4: Greedy Choice with Running State

Problem type: Problems where you track a running value (sum, maximum, minimum) and make greedy decisions based on it.

Greedy strategy: Maintain state that captures the "best so far" and update greedily.

The invariant on the running state rules out any better solution that the algorithm could have reached from this point.

Problems using this pattern:

Pattern 5: Huffman-Style / Priority Queue Greedy

Problem type: Problems where you repeatedly select the smallest/largest elements and combine them.

Greedy strategy: Use a heap to always process the optimal element first.

Processing elements in heap order keeps every combination step locally optimal, which is what each of these problems requires.

Problems using this pattern:

Most greedy solutions follow a similar structure:

A few decisions shape every greedy solution that follows this template:

Here is a complete example that runs through the greedy approach end to end.

Problem: You have a knapsack that can hold weight W. Given n items, each with a weight and value, maximize the total value you can carry. Unlike 0/1 knapsack, you can take fractions of items.

Example:

Step 1: Identify the Greedy Criterion

What makes an item "attractive"? Neither weight alone nor value alone tells the full story. The criterion that does is value per unit weight (value density).

Step 2: Sort by Greedy Criterion

Sort items by value/weight in descending order: Item 1, Item 2, Item 3.

Step 3: Make Greedy Choices

Implementation

Why Greedy Works Here

Fractional knapsack satisfies the greedy choice property. Taking the highest ratio item first maximizes the value extracted per unit of weight. Because items can be split, there is no blocking effect: a high-ratio item never locks the knapsack into a bad state, since any remaining capacity can still be filled optimally with the next-best ratios. Each greedy choice therefore leaves behind a subproblem that is itself solved optimally by the same rule.

The exchange argument makes this concrete. Suppose an optimal solution takes less of a higher-ratio item X and more of a lower-ratio item Y. Move a small amount of weight w from Y into X. The total weight stays the same, but the total value changes by w * (ratio(X) - ratio(Y)), which is positive. So the optimal solution can only improve by moving toward the greedy choice, which means the greedy choice was optimal to begin with.

Contrast with 0/1 Knapsack

The 0/1 version forbids fractions: each item is taken whole or skipped. Greedy by value/weight ratio breaks here.

Consider capacity W = 50 with three items:

Greedy by ratio: take item 1 (weight 10, value 60), then item 2 (weight 20, value 100). Total weight = 30, total value = 160. Remaining capacity = 20, but item 3 weighs 30 and cannot fit. Final greedy value = 160.

Optimal: skip item 1, take items 2 and 3. Total weight = 50, total value = 220.

The reason greedy fails is that the exchange argument no longer goes through. In the fractional case, the proof relied on moving a small amount of weight from one item to another. Without divisibility, the smallest valid move is "swap one whole item for another whole item," and a swap of that size can change the total weight by enough to violate the capacity constraint. Committing to item 1 leaves only 20 units of capacity, which is not enough room for item 3, and that loss cannot be recovered by partial substitution. The earlier choice has locked out a strictly better combination, which is exactly the failure mode greedy was supposed to avoid. 0/1 knapsack needs dynamic programming.

Here is another classic greedy problem, this time with a different selection criterion.

Problem: Given n activities with start and end times, select the maximum number of non-overlapping activities.

Example:

The Greedy Criterion

Which activity should we pick first? A few plausible criteria, and how each behaves:

The criterion that holds up is earliest end time.

The Algorithm

Walkthrough

Implementation

Why Earliest End Time Works

By picking the activity that ends earliest, we maximize the remaining time available for other activities. Any other first choice would end later, leaving less room.

Proof by exchange argument: Suppose an optimal solution O does not start with the earliest-ending activity E. Let O start with activity A instead. Since E ends no later than A, we can replace A with E in O without causing any conflicts. Since E ends no later than A, any activity in O scheduled after A also starts after E's end time, so the swap stays valid. The modified solution is still valid and has the same count. Repeating this argument, we can transform any optimal solution into the greedy solution.

Mistake 1: Assuming Greedy Works Without Proof

Just because a problem looks like it should be greedy does not mean it is. Always verify with counterexamples.

Example: Coin change with denominations [1, 3, 4] and target 6.

Before committing to a greedy approach, try to construct a case where the greedy choice produces a suboptimal solution. If no such case exists, the approach is likely safe.

Mistake 2: Wrong Greedy Criterion

Choosing the wrong sorting or selection criterion leads to incorrect results.

Example: For interval scheduling, sorting by start time instead of end time gives wrong answers.

Mistake 3: Not Handling Edge Cases

Greedy algorithms often have subtle edge cases:

Always consider these before submitting.

Mistake 4: Greedy for Counting Problems

If the problem asks "how many ways" or "count all solutions," greedy usually does not apply. These typically need DP or backtracking.

Look for these indicators:

Red flags that greedy might not work: