Greedy algorithms

A greedy algorithm builds an answer one decision at a time, and at each step it grabs whatever looks best right now - the largest coin, the earliest-finishing meeting, the cheapest edge - without ever reconsidering. It's the most optimistic strategy in computer science: it assumes a trail of locally best moves lands on the globally best answer. Sometimes that faith is rewarded with a short, beautiful, provably optimal algorithm. Just as often it walks confidently off a cliff. The entire skill is knowing which is which - and that hinges on two precise properties. We'll build the intuition on interval scheduling, where the right greedy rule is optimal and a very plausible wrong one quietly loses.

Two properties that make greedy safe

Greedy is not a heuristic you cross your fingers on - for a specific class of problems it is provably optimal. A problem is safely greedy when it has both of these at once:

1. The greedy-choice property. There exists a locally optimal choice - decided from what's in front of you, without solving any subproblem first - that is part of some globally optimal solution. In plain terms: making the greedy pick now never forecloses your ability to reach a best answer. (Contrast this with DP, which must first solve subproblems before it can compare options.)

2. Optimal substructure. Once you've locked in that first choice, what remains is a smaller instance of the same problem, and an optimal solution to the whole is the greedy choice plus an optimal solution to that remainder. This is the same property DP relies on - it's what lets you recurse. Greedy just adds the stronger promise that you don't have to explore the remainder's options; the rule picks correctly again.

Activity selection: pick the earliest finish

Here is the canonical greedy problem. You're given a set of activities, each with a start and finish time, and a single resource (one room, one CPU). Two activities conflict if they overlap in time. Goal: schedule the maximum number of non-conflicting activities. The winning greedy rule is almost suspiciously simple: repeatedly take the compatible activity that finishes earliest. Finishing early frees the resource soonest, leaving the most room for everything after.

The playground below lets you feel why the rule matters. Drag any bar left or right to change when that activity happens, then pick a greedy rule and step through the scan. Watch the same input give a maximum set under "earliest finish" - and a smaller, worse set under two rules that sound just as reasonable.

def activity_selection(activities):         # activities: list of (start, finish)
    activities.sort(key=lambda a: a[1])   # 1. sort by EARLIEST FINISH - the greedy key
    chosen, last_finish = [], float("-inf")
    for start, finish in activities:
        if start >= last_finish:            # compatible with everything kept so far?
            chosen.append((start, finish))
            last_finish = finish            # commit - this pick is never undone
    return chosen                          # provably a maximum-size compatible set

One sort plus one linear scan: $O(n\log n)$ total, dominated by the sort. No table, no recursion, no memory beyond the running last_finish. That economy is the whole appeal of greedy - when you can prove it works.

Why earliest-finish is optimal: the exchange argument

How do you prove a greedy rule is safe rather than just observing it on examples? The standard tool is the exchange argument: show that any optimal solution can be transformed, choice by choice, into the greedy one without ever getting worse. If the greedy solution is no worse than an arbitrary optimum, it is itself optimal.

This "an optimal solution can be nudged toward the greedy one" template proves most greedy algorithms. It's also why Huffman coding - repeatedly merging the two least-frequent symbols to build an optimal prefix code - is correct: the two rarest symbols can always be pushed to the deepest, longest codewords of some optimal tree, so merging them first is safe. Same exchange idea, different problem.

Greedy vs. DP: commit, or explore?

The cleanest way to hold these two apart: both need optimal substructure, but they differ on how much they trust a local choice. DP assumes nothing - at each subproblem it evaluates every option and keeps the best, paying with a table and $O(mn)$-style time. Greedy assumes the local rule is always right - it commits to one option and pays almost nothing. Greedy is a strict special case: when the greedy-choice property holds, the DP's "try everything" collapses to "try the one obvious thing," and an $O(2^n)$ or $O(mn)$ algorithm becomes $O(n\log n)$. When it doesn't hold, that shortcut silently returns a wrong answer - which is exactly what you watched two of the three rules do above.

Check yourself