Patterns

Greedy choices

A greedy algorithm commits to a choice and does not take it back. That is a feature when the choice is safe, and it is a bug when a later item would have made an earlier commitment look foolish. The skill is not "be greedy." The skill is knowing a proof, even a short one, that the choice cannot ruin the optimum.

This page works an original scheduling example where the proof is real, then shows a nearby rule that sounds just as reasonable and fails. The contrast is the lesson. Dynamic programming is what you use when you cannot throw the alternatives away. Heaps sometimes implement a greedy rule efficiently. They are not a substitute for the proof.

A choice you can defend

Original task: meetings are pairs (start, end) on a single calendar. Ends are exclusive, so a meeting that ends at 10 does not conflict with one that starts at 10. Return the largest number of meetings you can attend. You may not attend overlapping meetings. You may reorder the list.

The greedy rule: repeatedly attend the meeting that ends soonest among the meetings that start at or after you are free. Sorting by end time makes that rule a single scan.

def max_meetings(meetings: list[tuple[int, int]]) -> int:
    ordered = sorted(meetings, key=lambda meeting: meeting[1])
    attended = 0
    free_at = float("-inf")
    for start, end in ordered:
        if start >= free_at:
            attended += 1
            free_at = end
    return attended


assert max_meetings([(1, 4), (2, 3), (3, 5)]) == 2
assert max_meetings([(0, 10), (1, 2), (2, 3)]) == 2
assert max_meetings([]) == 0

Sort by ending time, which is O(n log n) for n meetings, and then scan once. The scan is linear. Extra space is the sorted copy, linear if sorted allocates, or constant extra beyond the input if you are allowed to sort a copy you already own. The dominant term is the sort.

Walk the first assert. Sorted by end: (2, 3), (1, 4), (3, 5). You take (2, 3) and become free at 3. (1, 4) starts too early. (3, 5) starts as you become free, so you take it. Two meetings. Taking the long meeting (1, 4) first would block both of the others and leave you with one. The greedy rule refuses that trap because (1, 4) does not end soonest.

Why the rule is safe, in one paragraph you can say out loud: consider an optimal schedule. Look at its first meeting. If it is not the meeting that ends soonest, you can swap in the soonest-ending meeting that is still compatible with time zero. That swap does not create an overlap with the rest of the optimal schedule, because the replacement ends even earlier. The count stays the same. Repeating the argument for the next slot shows that following the rule never does worse than an optimum. You do not need heavier machinery than that for this problem. If you cannot tell a swap story, do not call the algorithm greedy. Call it a heuristic and look for a counterexample.

A rule that sounds fine and is wrong

Sorting by start time and taking every meeting that fits is a different rule. It fails on the second assert. Ordered by start: (0, 10), (1, 2), (2, 3). You take (0, 10) and then nothing else, and you attend one meeting. The optimum is two: (1, 2) and (2, 3). The earliest start was the worst commitment. Greedy is not "sort by whatever field is lying around."

Shortest duration is another tempting rule, and it also fails. Imagine meetings (0, 5), (5, 6), and (6, 100) beside a short meeting (4, 7) that overlaps both of the first two useful ones. You should construct a counterexample on paper before you trust a new field. Five minutes with three intervals saves you from coding the wrong sort. This is the same discipline as a mean unit test, applied before the code exists.

Greedy versus a table

The hop-count problem on the dynamic programming page is not solved by "always hop 2." Always hopping 2 can miss the stone or miss some of the sequences if the task is to count them. Counting requires the table, or an equivalent recursion with memory. Selecting a maximum set of compatible meetings does not, because the swap argument says one specific choice is always enough.

When you are unsure, try to break your rule with four items. If you cannot break it, try to say the swap argument. If you cannot say it, reach for dynamic programming or for a search, and tell the interviewer that you do not yet have a greedy proof. That sentence is worth more than a wrong O(n log n) solution presented with confidence. The common mistakes page includes "naming a pattern you did not justify" for this reason.

Implementation details that change the answer

The comparison start >= free_at encodes the exclusive end. If ends were inclusive, back-to-back meetings would conflict and the comparison would be start > free_at. Read the prompt. This is a one-character bug with a large effect, and the sample data often uses gaps that hide it. Add an assert where one meeting starts exactly when another ends.

Also decide whether a meeting with start == end is a real meeting. This function would accept it, because the start is not before free_at and it then sets free_at to that same instant. If a zero-length meeting should be rejected, filter it before the loop. Do not leave that decision inside a sort key.

If the prompt asks which meetings, not only how many, store the chosen pairs in a list when you attend them. The counting argument does not change. If the prompt asks for the maximum total duration instead of the maximum count, the soonest-ending rule is no longer justified. A short meeting that ends early can block a long one. That variant needs a different approach. Noticing the objective change is part of reading, which the arrays and hashing page also nags you about: the noun in the prompt picks the algorithm.

Practice drill

Implement max_meetings from memory. Add the back-to-back assert (0, 5) and (5, 7) and confirm the result is 2 under an exclusive end. Then write the start-time rule beside it and assert that the two functions disagree on [(0, 10), (1, 2), (2, 3)]. Keep that disagreeing assert. It is documentation of why the sort key exists.

Then change the objective, on paper only, to "maximum total duration." Find a three-meeting counterexample to the soonest-ending rule. You do not need to code the replacement algorithm tonight. You need to feel the proof disappear. Tomorrow, if you want a follow-up, the heap page's priority queue can pick among candidate meetings by end time in an online stream. The proof stays the same. The container changes because the input arrives over time instead of sitting in a list you can sort up front.