Greedy Fundamentals & Intervals

Why greedy works

Greedy algorithms make a locally optimal choice and rely on a proof that the choice never blocks an optimal solution. The two classic proof tools:

• Exchange argument: swap your choice into an optimal solution
• Stays-ahead argument: show your choice is never worse at any step

If you cannot prove this, greedy is risky.

Interval scheduling (activity selection)

Goal: pick the maximum number of non-overlapping intervals.

Algorithm:

1. Sort by end time
2. Take the earliest finishing interval
3. Repeat with the remaining intervals that start after the last end

Why it works: choosing the earliest finish leaves the most room for the rest.

Complexity: O(n log n) for the sort.

Optimal merge pattern (Huffman-like)

Given costs to merge two items (a + b), always merge the two smallest first.

Use a min-heap:

1. Push all sizes into a heap
2. Pop two smallest, add their sum to total
3. Push sum back

This is identical to the core step in Huffman coding.

Greedy pitfalls

• Sorting by the wrong key (start time instead of end time)
• Thinking greedy works without a proof
• Ignoring ties (decide consistent tie-breaking)

What you will build

• Maximum number of non-overlapping intervals.
• Minimum total merge cost.