A Greedy Choice Inside Divide and Conquer

Mission

Three-hour route

Start here — two questions about every algorithm

A greedy algorithm commits to a next choice using information available now. Divide and conquer changes the size of the question: solve smaller copies, then combine their results. They can appear in the same algorithm, but the split itself is not automatically a greedy choice. We must identify the exact line where a local choice is made and prove the information at that line is sufficient.

Part 1 — Dijkstra is greedy, precisely

The algorithm does not greedily choose the cheapest next road. It greedily settles the unfinished suburb with the smallest total distance from the start. Press Play and read the amber sentence on every step.

Part 2 — The schedule needs an order

The events arrive as A, D, B, E, C. How can our own code produce B, C, D, E, A before the greedy scan? That is the divide-and-conquer task in Part 4.

# The exchange argument in plain Python words# Let E be the compatible event that ends earliest.# If an optimal schedule starts with some other event X,# replace X with E.# E ends no later than X, so every later event still fits.# Therefore an optimal schedule exists that starts with E.

Worked example 1 — one long event or four short ones?

Suppose A runs from 09:00 to 12:00. B, C, D and E form a chain from 09:30 to 11:30. Picking the event that starts first sounds sensible, but it uses the wrong measurement: we want to leave room for as many later events as possible. Run both rules on the same input below.

For these times, E is B (finishes 10:00), while X could be A (finishes 12:00). Replacing A with B makes C, D and E available. Equality matters: an event starting exactly when the previous one ends is compatible.

Part 3 — A greedy rule needs a reason

'It feels efficient' is not a proof. A single counterexample is enough to reject a rule. Toggle the two coin strategies below.

Part 4 — Split, solve, merge

We will sort the actual five activities by finish time. The split happens at the midpoint. The interesting choice comes during merge: from two sorted halves, repeatedly take the front event that finishes earlier.

The merged order now flows straight into the greedy scheduler. Click through the same B → C → D → E → A order; A is rejected because it overlaps the chosen activities.

Worked example 2 — every step of the merge

Start with the unsorted finish times A12:00, D11:00, B10:00, E11:30, C10:30. The recursive calls must finish before the final merge begins. Here is the complete call structure; arrows on the way back mean that smaller answers have been solved.

merge_sort([A, D, B, E, C])├─ merge_sort([A, D])│  ├─ [A]    └─ [D]     → [D, A]└─ merge_sort([B, E, C])   ├─ [B]    └─ [E, C]  → [B] + [C, E] → [B, C, E]final merge: [D, A] + [B, C, E] → [B, C, D, E, A]

Now pretend you are the merge function. While both halves contain items, compare only the two current fronts and advance the chosen side. The table shows four comparisons, then the final leftover append.

Worked example 3 — the same pattern finds a top three

The connection is not limited to event times. Imagine eight scores in input order: A42, B91, C35, D18, E76, F65, G20, H88. Split them into two groups of four. Each half returns only its own top three in descending order. The final combine step greedily takes the larger front until it has three names.

def top_k(values, k):    """Return the k highest (name, score) pairs, highest first."""    if k <= 0 or not values:        return []    if len(values) == 1:        return values[:]    middle = len(values) // 2    left = top_k(values[:middle], k)    # solved left half    right = top_k(values[middle:], k)   # solved right half    answer = []    i = j = 0    while len(answer) < k and (i < len(left) or j < len(right)):        # Both halves are sorted high to low. The higher front is next.        if j == len(right) or (i < len(left) and left[i][1] >= right[j][1]):            answer.append(left[i])            i += 1        else:            answer.append(right[j])            j += 1    return answerscores = [("A", 42), ("B", 91), ("C", 35), ("D", 18),          ("E", 76), ("F", 65), ("G", 20), ("H", 88)]assert top_k(scores, 3) == [("B", 91), ("H", 88), ("E", 76)]

Practice

frontier = [("Town Hall", 5), ("Museum", 7)]# choose one pair

events = [("B", 9.5, 10.0), ("C", 10.0, 10.5),          ("D", 10.5, 11.0), ("E", 11.0, 11.5),          ("A", 9.0, 12.0)]

greedy_change(6, [1, 3, 4])  # [4, 1, 1]  -> 3 coins# better answer: [3, 3]         -> 2 coins

left  = [("D", 10.5, 11.0), ("A", 9.0, 12.0)]right = [("B", 9.5, 10.0), ("C", 10.0, 10.5),         ("E", 11.0, 11.5)]# [event[0] for event in merge(left, right, key=lambda e: e[2])]# returns ["B", "C", "D", "E", "A"]

Stop and explain — three new cases

For each case, write a candidate set, a local rule, and the assumption or counterexample. Predict before opening the explanation.

Student work area

TODO 7 makes the safe greedy choice inside merge. TODO 8 recursively builds sorted halves. TODO 2 passes that sorted result into the activity scheduler, and TODO 3 greedily keeps compatible events. The remaining TODOs test the rules and their limits.

# greedy_tutorial.py — write and test every ruledef compatible(event, last_end):    """An event is (name, start, end)."""    # TODO 1: Can this event start after the last chosen event ends?    passdef choose_activities(events):    """Merge-sort by finish time, then greedily select activities."""    # TODO 2: use YOUR merge_sort with key=lambda event: event[2].    # The function is defined below; Python looks it up when this runs.    ordered = []    chosen = []    last_end = 0    # TODO 3: scan ordered. Append only compatible events.    for event in ordered:        pass    return chosendef greedy_change(amount, coins):    """Repeatedly take the largest usable coin."""    # TODO 4: return the actual list of coins chosen, not just its length.    passdef better_schedule(first, second):    """Return the schedule containing more events.    If tied, return the one that finishes earlier.    """    # TODO 5: define exactly what 'better' means, including empty schedules.    passdef all_schedules(events, at=0, picked=None):    """Extension: recursively generate schedules for a tiny input."""    # TODO 6: use this only to CHECK a greedy rule on small data.    passdef merge(left, right, key=lambda value: value):    # TODO 7 — left and right are already sorted by key.    # Return one new sorted list containing every value from both lists.    # Compare key(left[i]) and key(right[j]); move one index.    # On a tie, take LEFT first so equal keys keep their original order.    return []def merge_sort(values, key=lambda value: value):    # TODO 8 — divide and conquer.    # Base case: a list of length 0 or 1 is already sorted.    # Split; recursively sort both halves with the SAME key; merge by key.    return []

Part 5 — Check, then explain

EVENTS = [    ("Harbour tour", 9.0, 12.0),    ("Opera",       10.5, 11.0),    ("Gallery",      9.5, 10.0),    ("Lunch",       11.0, 11.5),    ("Coffee",      10.0, 10.5),]original = EVENTS[:]answer = choose_activities(EVENTS)assert compatible(("back-to-back", 10.0, 10.5), 10.0)assert [event[0] for event in answer] == ["Gallery", "Coffee", "Opera", "Lunch"]assert greedy_change(6, [1, 3, 4]) == [4, 1, 1]  # greedy runs; it is not optimalassert better_schedule([], answer) == answerassert better_schedule(answer[:3], answer) == answersmall = [("B", 9.5, 10.0), ("C", 10.0, 10.5)]assert len(all_schedules(small)) == 4  # [], [B], [C], [B, C]assert merge([1, 5], [2, 3]) == [1, 2, 3, 5]assert merge([("left", 10)], [("right", 10)], key=lambda item: item[1]) == [    ("left", 10), ("right", 10)]assert merge_sort([7, 3, 8, 2, 5, 1]) == [1, 2, 3, 5, 7, 8]assert [event[0] for event in merge_sort(EVENTS, key=lambda event: event[2])] == [    "Gallery", "Coffee", "Opera", "Lunch", "Harbour tour"]assert EVENTS == original  # the original input was not changedprint("Merge sort prepared the activities; greedy selection chose four.")

In the terminal

$ python3 greedy_tutorial.pyMerge sort prepared the activities; greedy selection chose four.

TODO contract

Teacher checkpoints

Exit ticket