We use necessary cookies to run the site (sign-in and language). If you accept, we also load Google Analytics to see which pages are used, and Google reCAPTCHA to keep spam off the contact and bug-report forms. Privacy policy

← Blog
How to prepare

Greedy algorithm: how to know the greed is safe, plus three worked problems

· 2026-11-11

Short answer. A greedy algorithm makes the best local choice at every step. It never backtracks. It is correct only when no swap can improve that choice. That is called the exchange argument. Time is usually O(n log n) because of a sort. Below: trigger words, the safety check, Python code and three worked problems.

What is a greedy algorithm?

You face a sequence of decisions. At each step you take the option that looks best right now. You never go back, and you never search.

That makes it fast and short. It is not always right. Coins [1, 3, 4] with amount 6 break it. Greedy takes 4, 1, 1 instead of 3, 3.

So the main question about any greedy algorithm is always the same. Why does the local choice not hurt the global answer?

Paying 18 with the fewest coins, greedily
minCoinsGreedy([1, 5, 2, 10], 18)
coins
1
5
2
10
amount = 18
used
empty

Pay 18 with as few coins as possible. Greedy rule: always take the biggest coin that still fits.

Speed race
Every subset and the greedy pick on the same 11 meetings: the most that fit without overlapping

Bars: when each meeting ends, in the order the meetings start.

One operation is one meeting checked or one comparison while sorting. Every frame, each lane does the same number of operations, so the slow one falls behind.

Every subset O(2ⁿ·n)
0 operations
Greedy by end time O(n log n)
0 operations

 

And with more numbers

Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.

n = 10
Every subset2.2K · under 1 ms
Greedy by end time33.3 · under 1 ms
n = 20
Every subset2.2M · 22 ms
Greedy by end time80.5 · under 1 ms
n = 40
Every subset2.3T · 6.4 h
Greedy by end time189 · under 1 ms

The pattern page: when to use it, and a template in six languages

How do you prove a greedy algorithm is correct?

The exchange argument. Take any optimal solution. Show that its first step can be swapped for the greedy step. Nothing gets worse. Repeat for every step. So the greedy solution is at least as good.

In an interview you do not write the full proof. Name the swap and say why it changes nothing.

The second check: try to build a counterexample. None found in a minute, greed is probably safe. Found one, you need dynamic programming.

When does a problem need a greedy algorithm?

  • "Maximum number of non-overlapping intervals."
  • "Minimum number of jumps", "minimum number of refuelling stops".
  • "Assign cookies", "assign tasks" with one criterion.
  • "Can you reach the end", "minimum number of arrows".

The shared signal: one sorting rule, then the answer builds in one pass. Two rules that fight each other usually mean greed fails.

What does one greedy run look like?

Interval scheduling. Intervals [1, 4], [3, 5], [0, 6], then [5, 7] and [8, 9]. Pick the most non-overlapping ones. Sort by end, and the order stays the same.

Take [1, 4], end 4. [3, 5] starts before 4, skip. [0, 6] skip. [5, 7] starts at 5, take it, end 7. [8, 9] take. Answer 3.

The exchange: any optimal solution can begin with the earliest-ending interval. It leaves the most room for the rest.

How do you write a greedy algorithm in Python?

def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])      # by end
    count, end = 0, float("-inf")
    for s, e in intervals:
        if s >= end:
            count += 1
            end = e
    return count

def can_jump(nums):
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False                    # unreachable
        reach = max(reach, i + step)
    return True

def min_jumps(nums):
    jumps = cur_end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:                    # edge of the current jump
            jumps += 1
            cur_end = farthest
    return jumps

def assign_cookies(children, cookies):
    children.sort(); cookies.sort()
    i = j = 0
    while i < len(children) and j < len(cookies):
        if cookies[j] >= children[i]:
            i += 1                          # child satisfied
        j += 1
    return i

All four are one pass, with or without a sort first. That is the strength of the pattern.

How does greedy compare with its neighbours?

PatternHow it choosesCorrect whenTime
Greedy algorithmBest local step, no undoAn exchange argument existsO(n log n)
Dynamic programmingSearches states, remembers answersAlways, given a stateO(n · states)
BacktrackingSearches with undoAlways, but exponentialO(2ⁿ) or worse
Binary search on the answerVerifies a guessThe check is monotonicO(n log R)

How does greedy solve Jump Game?

An array of jump lengths. From index i you can jump up to nums[i] forward. Can you reach the end? Track the farthest reachable index. Walk left to right. An index beyond reach means no. Otherwise update the maximum.

The exchange: how you reached index i does not matter. Only that you did. So one number is enough.

How does greedy solve Gas Station?

A ring of stations. Each has fuel and a cost to reach the next. Where do you start to complete the loop? Total fuel below total cost means no answer. Otherwise drive with a tank. Tank goes negative: move the start to the next station. Reset the tank.

The exchange: start s cannot reach i. Then no station between them can either. Skip them all at once.

What mistakes break a greedy algorithm?

  • Sorting by start instead of end in interval scheduling. One long early interval eats everything.
  • Applying greed to coins of arbitrary values.
  • Skipping the total balance check in Gas Station and looping forever.
  • Going greedy where two criteria conflict. That needs DP.

How do you explain a greedy algorithm in an interview?

State the choice rule in one sentence. Then the exchange argument right away. Why does swapping any step for the greedy one lose nothing? Then code.

If unsure, say so out loud. "Let me test the greed on a counterexample" sounds better than a confident wrong answer.

Drill this pattern on the greedy page. Interval problems live on the intervals page.

FAQ

Why does greedy work for coins 1, 5, 10, 25?

The values are arranged so that a larger coin is never a bad idea. For 1, 3, 4 that fails. The property is called a canonical coin system.

How do you decide between greedy and DP?

Spend a minute trying to break the greed with a small example. Cannot: look for the exchange argument. Can: write the table.

Is Dijkstra a greedy algorithm?

Yes. It takes the closest node and never revisits it. The exchange argument: with non-negative weights, no detour is shorter.

Where do greedy algorithms show up in real systems?

Huffman coding gives the most frequent symbols the shortest codes. Schedulers pick the earliest deadline first. Caches evict the least recently used entry.