Greedy Algorithms: When a Local Choice Is Safe

Efficiency needs a correctness argument

Greedy algorithms usually sort or repeatedly select a locally preferred option. Their implementation may take O(n log n) or even linear time, but speed does not establish correctness. A proof often uses an exchange argument: take an optimal solution, show that its first choice can be replaced by the greedy choice without making the solution worse, then apply the same reasoning to the remaining subproblem.

Another common proof establishes an invariant: after each step, the partial greedy solution can still be extended to an optimal complete solution. If you cannot justify the local choice, test small counterexamples and consider dynamic programming, shortest paths, or exhaustive search instead.

Example: select the most non-overlapping intervals

For intervals with start and end times, sort by finish time. Always choose the compatible interval that ends earliest; it leaves as much room as possible for later choices.

def max_non_overlapping(intervals):
    intervals = sorted(intervals, key=lambda item: item[1])
    chosen = []
    last_end = float("-inf")
    for start, end in intervals:
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen

Sorting dominates, giving O(n log n) time and O(n) space if the sorted copy and result are included. For the proof, compare the earliest-finishing interval with the first interval in any optimal schedule: replacing that first interval cannot block a later choice that was previously possible, because the greedy interval ends no later.

Recognizing when a greedy rule fails

Picking the largest immediate reward, smallest item, or first available option is not universally optimal. In coin change, for example, choosing the largest coin not exceeding the remainder works for some denomination systems but fails for others. Knapsack with fractional items has a greedy value-per-weight rule; 0/1 knapsack generally requires dynamic programming because an item cannot be partially selected.

• State the greedy choice precisely, including tie-breaking.
• Look for an exchange or invariant proof.
• Compare the rule against brute force on tiny examples while developing the solution.
• Separate feasibility from optimization: a local choice may preserve validity without maximizing the objective.