Non-Overlapping Intervals: Greedy Interval Scheduling

Greedy algorithms build solutions incrementally by making the locally optimal choice at each step, hoping to find the global optimum. The challenge is proving that the greedy choice property holds: that making the locally optimal choice at each step leads to a globally optimal solution. For this problem, we identify the greedy criterion by analyzing what choice maximizes our progress toward the goal at each step. Sort the input if needed, then iterate through elements making irrevocable decisions. Unlike dynamic programming, greedy algorithms do not reconsider previous choices, which makes them efficient but requires careful correctness proofs. Common greedy strategies include activity selection (choose the earliest finishing task), fractional knapsack (choose the highest value-to-weight ratio), and Huffman coding (combine the two least frequent elements). Interval scheduling problems are classic greedy applications: sort intervals by end time and select non-overlapping intervals greedily. The time complexity of greedy algorithms is often dominated by the sorting step at O(n log n), with the greedy selection being O(n). When unsure if greedy works, try to find a counterexample. If you cannot, consider proving correctness using an exchange argument: show that swapping any non-greedy choice with the greedy choice does not worsen the solution.