The Greedy Idea & When It Fails

A greedy algorithm builds the answer one step at a time, and at every step takes the option that looks best right now. It never reconsiders: a choice once made is final.

That makes greedy algorithms short and fast, usually a sort plus one pass, O(n log n). The catch is that "best right now" is not always "best overall". A greedy algorithm is correct only when two things hold:

• Greedy-choice property: some optimal answer starts with the greedy choice.
• Optimal substructure: after that choice, what remains is a smaller copy of the same problem.

So greedy is never "obviously right". You pick a rule, then you either prove it or break it with a counterexample.

Take any optimal schedule and look at its first activity o₁. Greedy's first pick g finishes earliest of all, so end(g) ≤ end(o₁). Replace o₁ with g: nothing that came after o₁ can overlap g, the count stays the same, so the new schedule is still optimal and now starts with the greedy choice.

Repeat the argument on the rest of the timeline and you transform the optimal schedule into the greedy one, step by step, without ever losing an activity.

This exchange argument is the standard way to prove a greedy rule: show you can swap the greedy choice into an optimal solution without making it worse. Other "natural" rules fail it: earliest start loses to one long activity, shortest first loses to a short one that overlaps two others.