Unit 6 — Greedy

A festival publishes the start and end time of every event, but several overlap. How can you attend as many complete events as possible? A greedy algorithm sorts by the right key, then sweeps once and takes each locally best choice that still fits.

Each idea comes as a short ladder — the core choice on a tiny hand-traceable case, then the full stdin solver, then a counterexample showing when a greedy rule FAILS.

You will learn

Recognize a greedy problem, where taking the best choice each time builds the best answer.
Pick the right sort key and sweep the sorted items once.
Explain with an exchange argument why a greedy choice is safe.
Spot when greedy fails, and test small counter-examples before trusting it.

Lesson 1 — Choose the Event That Ends First

An early-starting event might last all day and block several short events. The safe local choice is the available event that ends first, leaving as much time as possible for what comes later. The sort key is part of the algorithm.

events = [(1, 4), (3, 5), (0, 7), (5, 7)]

def end_time(event):
    return event[1]

ordered = sorted(events, key=end_time)
print(ordered)

Output

[(1, 4), (3, 5), (0, 7), (5, 7)]

Notice

sorted(events, key=end_time) (a NAMED key, never a lambda) orders the events by their end time — the sort key IS the algorithm.

attended = 0
last_end = -1
for event in ordered:
    if event[0] >= last_end:
        attended = attended + 1
        last_end = event[1]
print(attended)

Output

Notice

Sweep once, taking an event when its start is >= last_end; the >= (not >) accepts an event that starts exactly when the last one ends — touching events do not overlap, so the greedy takes both.

Put it together: the full program reads n then the n events from stdin, sorts by end, sweeps, and prints how many were attended.

Try it yourself

import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
events = []
for position in range(n):
    start = int(tokens[1 + position * 2])
    end = int(tokens[2 + position * 2])
    events.append((start, end))

def end_time(event):
    return event[1]

ordered = sorted(events, key=end_time)
attended = 0
last_end = -1
for event in ordered:
    start = event[0]
    end = event[1]
    if start >= last_end:
        attended = attended + 1
        last_end = end
print(str(attended))

Run the full solver from this unit folder:

python assets/l1.py < assets/l1/1.in

Notice

The full program reads n and the events from stdin, sorts by end, sweeps once, and prints how many fit — the same greedy on real input.

Complexity: sorting the events is O(n log n); the sweep is O(n).

Greedy Choices Need the Right Key

A plausible key can be wrong. Watch greedy by start time on the same kind of input.

events = [(0, 10), (1, 2), (3, 4)]

def start_time(event):
    return event[0]

ordered = sorted(events, key=start_time)
attended = 0
last_end = -1
for event in ordered:
    if event[0] >= last_end:
        attended = attended + 1
        last_end = event[1]
print(attended)

Output

Notice

Greedy by start attends only 1 event here (it takes the long (0,10) and blocks the rest); greedy by end (Lesson-1 rung 2) attends 2 — the earliest-END key is the safe one.

Why the Earliest End Is Safe

Suppose a best schedule starts with some other event. Swap it for the earliest-ending available event: the swap frees the schedule at the same time or sooner, so it cannot block any later event. There is always a best schedule that begins with the greedy choice, and the same reasoning repeats. This swap story is the exchange argument — replace one choice in a best answer with the greedy choice without making the answer worse.

Lesson 2 — Match the Choice to the Goal

Different goals need different local choices. To make change with safe coin values, take the largest coin first: integer division // counts how many fit, and % leaves the amount still needed.

amount = 99
coins = [25, 10, 5, 1]
coins.sort(reverse=True)
used = 0
for coin in coins:
    used = used + amount // coin
    amount = amount % coin
print(used)

Output

Notice

Largest-coin-first on 25/10/5/1 gives 9 coins for 99 (3*25 + 2*10 + 4*1).

Put it together: the coin solver reads the amount from stdin and prints the coin count.

Try it yourself

import sys

data = sys.stdin.read()
amount = int(data.strip())
coins = [25, 10, 5, 1]
coins.sort(reverse=True)
used = 0
for coin in coins:
    used = used + amount // coin
    amount = amount % coin
print(str(used))

Run the full solver from this unit folder:

python assets/l2.py < assets/l2/1.in

Notice

The coin solver reads the amount from stdin and prints the coin count with the same largest-first loop.

Complexity: one pass over the fixed coin set — O(1) here (O(k) for k coin values).

When Greedy Coins FAIL

Greedy-largest is only safe for some coin systems. Try coins 4, 3, 1 for 6.

amount = 6
coins = [4, 3, 1]
used = 0
for coin in coins:
    used = used + amount // coin
    amount = amount % coin
print(used)

Output

Notice

Greedy uses 3 coins (4 + 1 + 1), but 3 + 3 uses only 2 — greedy fails for this coin system. Before trusting a greedy rule, tell the exchange story: why can the greedy choice replace another without making the answer worse?

Pair Small with Small

Robots on a line each need one charging station. To minimize total walking distance, sort both position lists and pair them in order. The why is an exchange argument on crossed pairs — demonstrate it on a tiny case.

robots = [1, 10]
stations = [50, 6]
crossed = abs(robots[0] - stations[0]) + abs(robots[1] - stations[1])

robots.sort()
stations.sort()
uncrossed = abs(robots[0] - stations[0]) + abs(robots[1] - stations[1])
print(crossed)
print(uncrossed)

Output

53
45

Notice

The crossed pairing costs 53; sorting both lists and pairing in order costs 45 — uncrossing two crossed pairs never increases the total (the exchange argument).

Put it together: the pairing solver reads the robot and station positions from stdin, sorts both, and prints the total distance.

Try it yourself

import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
robots = []
stations = []
for position in range(n):
    robots.append(int(tokens[position + 1]))
    stations.append(int(tokens[n + position + 1]))
robots.sort()
stations.sort()

total_distance = 0
for position in range(n):
    total_distance = total_distance + abs(robots[position] - stations[position])
print(str(total_distance))

Run the full solver from this unit folder:

python assets/l3.py < assets/l3/1.in

Notice

The pairing solver reads both position lists from stdin, sorts each, and prints the total distance.

Complexity: sorting both lists is O(n log n); pairing is O(n).

Cheapest First Fits the Most

When every item counts equally and the goal is to select as many as possible under a budget, take the cheapest items first. Sweep the sorted costs, taking each while the running spend still fits.

costs = [9, 2, 4, 6, 10]
budget = 12
costs.sort()
spent = 0
selected = 0
for cost in costs:
    if spent + cost <= budget:
        spent = spent + cost
        selected = selected + 1
print(selected)

Output

Notice

Sorted costs 2, 4, 6, 9, 10 fit 2 + 4 + 6 = 12 → 3 items; the next (9) would exceed the budget. Replacing a costlier chosen item with a cheaper unchosen one never spends more, so cheapest-first is safe.

Put it together: the budget solver reads n, the budget, and the costs from stdin, sorts ascending, and prints how many fit.

Try it yourself

import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
budget = int(tokens[1])
costs = []
for position in range(n):
    costs.append(int(tokens[position + 2]))
costs.sort()

spent = 0
selected = 0
for cost in costs:
    if spent + cost <= budget:
        spent = spent + cost
        selected = selected + 1
print(str(selected))

Run the full solver from this unit folder:

python assets/l4.py < assets/l4/1.in

Notice

The budget solver reads n, the budget, and the costs from stdin, sorts ascending, and prints how many fit.

Complexity: sorting the costs is O(n log n); the budget sweep is O(n).

A Greedy Checklist

Name the goal and the locally best choice. Pick the sort key that brings that choice next, then sweep once storing only the state needed to decide whether to take it. Finally, test small counter-examples and tell the exchange story — why the greedy choice can replace another without making the answer worse.

Recap

For the most events, sort by END time and take each event that starts at or after the last end.
The sort key is the algorithm: sorting by start time can attend fewer events.
An exchange argument shows that swapping toward the greedy choice never makes the answer worse.
Largest-coin-first works for 25/10/5/1 but fails for 4/3/1 on 6; pairing sorted lists and cheapest-first are safe.
Name the goal, choose the key, sweep once, then test counter-examples.

You can now design a greedy solution and check that its choice is safe.