Greedy

Greedy | Algoryva

First, the naive way

Try every combination

Take this scheduling task: a room can host one activity at a time, and each activity has a start and end time. Pick as many activities as possible that do not overlap.

The safe-but-slow approach considers every subset of activities and keeps the largest one with no overlaps. With n activities there are 2ⁿ subsets, so 30 activities already means over a billion subsets to check.

python

from itertools import combinations

def max_activities_bruteforce(iv):
    best = 0
    for r in range(len(iv) + 1):
        for combo in combinations(iv, r):
            ordered = sorted(combo)
            if all(ordered[i][1] <= ordered[i + 1][0] for i in range(len(ordered) - 1)):
                best = max(best, r)
    return best

print(max_activities_bruteforce([(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9)]))   # 2

Cost: O(2ⁿ × n log n): fine for 15 activities, hopeless for 50.

Worked by hand

The scan by hand

Eleven activities sorted by end time. “Last end” is the finishing time of the most recent pick.

interval	starts at	last end	decision
1-4	1	none	pick (last end = 4)
3-5	3	4	skip: 3 < 4
0-6	0	4	skip: 0 < 4
5-7	5	4	pick (last end = 7)
3-9	3	7	skip
5-9	5	7	skip: 5 < 7
6-10	6	7	skip: 6 < 7
8-11	8	7	pick (last end = 11)
8-12	8	11	skip
2-14	2	11	skip
12-16	12	11	pick

1
Result
Four activities: 1-4, 5-7, 8-11, 12-16. Nothing fits a fifth.
2
Why sorting by end time matters
Sorting by start time sounds plausible but fails: one very long early activity (0-10) would block two short ones inside it (1-2 and 3-4). Taking the shortest first fails too: with 1-5, 4-7 and 6-10, the shortest is 4-7, and it overlaps both others, so you get 1 activity instead of 2.

Implementation

Interval scheduling, and a rule that fails

The correct rule is five lines. Next to it is the tempting but wrong “earliest start” rule, to show how a counterexample exposes a bad greedy.

Plan in plain steps

pseudocode

sort intervals by end time
last_end = -infinity; count = 0
for each interval in that order:
    if interval.start >= last_end: take it; last_end = interval.end

python

def max_activities(intervals):
    count, last_end = 0, float("-inf")
    for start, end in sorted(intervals, key=lambda x: x[1]):
        if start >= last_end:
            count += 1
            last_end = end
    return count

def by_earliest_start(intervals):        # plausible, but WRONG
    count, last_end = 0, float("-inf")
    for start, end in sorted(intervals):
        if start >= last_end:
            count += 1
            last_end = end
    return count

print(max_activities([(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]))   # 4
data = [(0, 10), (1, 2), (3, 4)]
print(by_earliest_start(data), max_activities(data))   # 1 2

Reading the code

›start >= last_end allows an interval that starts exactly when the previous one ends (touching, not overlapping). Use > if the problem says touching counts as overlapping.
›The wrong rule picks (0, 10) first because it starts earliest, and that single choice blocks both (1, 2) and (3, 4). The correct rule finds 2.
›The cost is the sort, O(n log n), plus one O(n) scan.

Implementation

Greedy that works, and greedy that does not

Largest-coin-first is correct for the standard coin system but wrong for others. The same code, different input.

python

def greedy_coins(coins, amount):
    n = 0
    for c in sorted(coins, reverse=True):
        n += amount // c
        amount %= c
    return n if amount == 0 else -1

print(greedy_coins([1, 5, 10, 25], 63))   # 6
print(greedy_coins([1, 3, 4], 6))   # 3

Reading the code

›For coins 1, 5, 10, 25 the greedy answer for 63 is 6 coins, which is optimal.
›For coins 1, 3, 4 and amount 6 greedy returns 3 (4 + 1 + 1), but the true minimum is 2 (3 + 3). The same algorithm is right on one input set and wrong on another.
›That is why correctness depends on the *problem*, not just the idea. Whenever greedy is in doubt, the Top-Down DP lesson gives the safe alternative.

Implementation

A greedy scan: can you reach the end?

Each position tells you how far you can jump at most. Can you reach the last position? Track the farthest position reachable so far; you never need to remember *how* you got there.

python

def can_reach_end(jumps):
    farthest = 0
    for i, j in enumerate(jumps):
        if i > farthest:
            return False
        farthest = max(farthest, i + j)
    return True

print(can_reach_end([2, 3, 1, 1, 4]))   # True
print(can_reach_end([3, 2, 1, 0, 4]))   # False

Reading the code

›farthest is the greedy summary of everything reachable. Positions at or before it are all reachable, because you can stop early on any jump.
›If the current index is beyond farthest, you are stuck: every earlier jump fell short.
›In [3, 2, 1, 0, 4] every route ends at index 3 (value 0), and index 4 is out of reach. One pass, O(n), O(1) space.

Worked problem

Assign cookies

The problem

Each child has a greed value (the smallest cookie size that satisfies them). Each cookie has a size and goes to at most one child. Maximise the number of satisfied children.

Sort children by greed and cookies by size.
Walk the cookies from smallest to largest. If a cookie satisfies the currently least-greedy unsatisfied child, give it to them and move to the next child.
Why it is safe: the smallest cookie that works for the least greedy child is never needed more elsewhere (an exchange argument), and a cookie too small for the least greedy child is too small for everyone.

python

def assign_cookies(greed, cookies):
    greed.sort()
    cookies.sort()
    child = 0
    for c in cookies:
        if child < len(greed) and c >= greed[child]:
            child += 1
    return child

print(assign_cookies([1, 2, 3], [1, 1]))   # 1
print(assign_cookies([1, 2], [1, 2, 3]))   # 2

Takeaway. Two sorted lists and one pass is the signature of a matching-style greedy. The sort puts the “cheapest sufficient” choices in order, and each cookie is used or discarded exactly once.

Worked problem

Fewest arrows to burst all balloons

The problem

Balloons are horizontal intervals [start, end]. An arrow shot straight up at position x bursts every balloon with start <= x <= end. Find the fewest arrows needed.

This is interval scheduling in disguise: each arrow handles one group of overlapping balloons.
Sort by end. Shoot the first arrow at the end of the first balloon (it bursts the most balloons that start early enough).
For each next balloon: if it starts after the arrow position, it was missed, so shoot a new arrow at its end.

python

def min_arrows(points):
    arrows, pos = 0, float("-inf")
    for s, e in sorted(points, key=lambda p: p[1]):
        if s > pos:
            arrows += 1
            pos = e
    return arrows

print(min_arrows([[10, 16], [2, 8], [1, 6], [7, 12]]))   # 2
print(min_arrows([[1, 2], [3, 4], [5, 6]]))   # 3

Takeaway. Shooting at the *end* of the earliest-ending balloon is the same exchange argument as before: it is the furthest right you can shoot while still bursting that balloon, so it catches the most later ones. Recognising a known pattern in new clothes is half of contest skill.

Wrap-up

Remember this

Greedy commits to the locally best choice at every step; it is fast but only sometimes correct.
It is valid when a greedy choice can be part of an optimal solution and what remains is the same kind of problem.
Exchange arguments justify a rule; tiny counterexamples refute one. Always try to break it.
Most greedy solutions are “sort by the right key, then scan once with a running value”.
When an early choice can block a better combination, use dynamic programming instead.

Cheat sheet

Idea: take the best-looking choice now, never reconsider
Valid when: greedy-choice property + optimal substructure
Prove it: exchange argument: swap the greedy choice into any optimal solution
Break it: try a tiny counterexample (coins 1, 3, 4 and amount 6)
Typical shape: sort by the right key, one pass with a running value
Cost: O(n log n) for the sort + O(n) scan

Top traps to avoid

Assuming a greedy rule is right because it passes the samples.
Sorting by the wrong key (start time or length instead of end time).
Using greedy where dynamic programming is needed (coins 1, 3, 4).

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What is the greedy rule for the maximum number of non-overlapping activities?
2.Greedy coin change with coins [1, 3, 4] and amount 6 returns 3. What is the true minimum?
3.What dominates the running time of sort-then-scan interval scheduling?
4.“Find the minimum number of meeting rooms so no two overlapping meetings share a room” most resembles:
5.What does an exchange argument show?
6.can_reach_end([3, 2, 1, 0, 4]) returns False. Why?
7.Pick the maximum number of non-overlapping intervals [(1,4),(3,5),(0,6),(5,7),(8,9)] by sorting on end time and taking each interval that starts at or after the last end. How many are picked?
8.Greedy coin change with coins [4, 3, 1] for amount 6 (always take the largest coin that fits). How many coins are used?
9.When is a greedy choice guaranteed to lead to an optimal answer?
10.Jump game on [2, 3, 1, 1, 4]: track the farthest reachable index. Is the last index reachable?
11.Jump game on [3, 2, 1, 0, 4]: is the last index reachable?
12.Activity selection after sorting the intervals by end time: what is the running time?
13.What does the exchange argument show when proving greedy correct?
14.Assign cookies to children: children need [1, 2, 3], cookies are [1, 1]. Give each cookie to the least-demanding child it satisfies. How many children are content?
15.Why does greedy fail for coin change with coins {1, 3, 4} and amount 6?

Greedy

After this lesson you will be able to

Builds on

Unlocks

Giving change with the biggest coins first

Try every combination

The activity that ends first leaves the most room

Sort by end time, then scan

When is greedy correct?

The scan by hand

Interval scheduling, and a rule that fails

Reading the code

Greedy that works, and greedy that does not

Reading the code

A greedy scan: can you reach the end?

Reading the code

Why greedy is fast

Edge cases

Mistakes to avoid

How to spot a greedy problem

Assign cookies

Fewest arrows to burst all balloons

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up2 problems

Core48 problems

Application9 problems

Challenge1 problem