Greedy Algorithms

A greedy algorithm builds a solution by committing to a locally preferred choice without revisiting it. This works only when the problem has a suitable exchange or dominance property.

Interval scheduling

Given activities with start and finish times, select the largest non-overlapping subset. Choosing the compatible activity that finishes earliest is optimal.

Exchange argument: take any optimal schedule. Its first activity cannot finish earlier than the greedy first activity. Replacing it with the greedy choice preserves feasibility and the number of scheduled activities. Apply the same argument to the remaining compatible activities.

After sorting by finish time, selection is linear, so total time is Θ(n log n) and additional selection space is Θ(1) excluding output.

When greedy fails

Choosing the item with the largest immediate value does not solve 0/1 knapsack in general. A local choice can consume capacity needed by a better combination. Fractional knapsack has different structure and does admit a greedy solution by value density.

Proof patterns

• exchange an optimal solution's first disagreement with the greedy choice;
• show the greedy solution stays at least as far ahead at every step;
• model feasible sets with a structure such as a matroid.

Exercises

1. Give a counterexample to choosing the shortest activity first.
2. Prove Kruskal's safe-edge choice using graph cuts.
3. Explain why non-negative edge weights are necessary for Dijkstra's greedy step.