Lesson 5 of 16

Greedy Choices

A greedy algorithm commits to the best-looking current choice and proceeds. Avoiding reconsideration can simplify a solution, but you need a reason why that choice leads to a correct final answer.

Should you take the largest coin first?

With coins worth 1, 3, and 4, making 6 greedily gives 4 + 1 + 1: three coins. Yet 3 + 3 uses two. The locally largest coin does not minimize the total number.

This is a counterexample. One counterexample disproves a claim that a method works on every input.

Choose the earliest-finishing meeting

Schedule as many non-overlapping meetings as possible in one room. All meetings have equal value, and a meeting may begin exactly when another ends.

meetings = [(0, 2), (1, 5), (2, 4), (4, 6)]
chosen = []
last_end = float("-inf")
for start, end in sorted(meetings, key=lambda item: item[1]):
    if start >= last_end:
        chosen.append((start, end))
        last_end = end
print(chosen)

The chosen meetings are [(0, 2), (2, 4), (4, 6)]. Taking the earliest-finishing meeting leaves the most time afterward.

If an optimal schedule starts with a different meeting, replace it with the earliest-finishing one. The later meetings still fit. This exchange argument justifies the first greedy choice, and the same reasoning applies to the remaining meetings.

Sorting takes O(n log n) and scanning takes O(n), for O(n log n) overall.

Reconsider when requirements change

If meetings earn different amounts, maximizing their count differs from maximizing revenue. Earliest finish does not guarantee maximum revenue. Greedy methods are neither universally wrong nor universally correct: justify the selection rule under the problem’s conditions.

Check your understanding

Meeting A runs 0–3, B runs 0–1, C runs 1–2, and D runs 2–3. Does choosing A first maximize the number of meetings?