Greedy Algorithms8 sections · 316 units
Open in Course

The Sorting Question

What to sort by?

In many greedy problems, the core idea is figuring out what to sort by. Common choices:

1.1. End time: : activity selection, interval scheduling

2.2. Start time: : merging intervals

3.3. Ratio: : fractional knapsack (value/weight)

4.4. Absolute value: : one quantity ascending, another descending

5.5. Deadline: : job scheduling Wrong sort order = wrong answer. Right sort order = optimal greedy solution. How do you find the right order? Try small examples. If sorting by X gives wrong answers, try Y.