Know this before you start: “Sort first, then decide in one pass”
Sort first, then decide in one pass
Many greedy problems become easy after sorting by the right key: then a single left-to-right pass makes each decision once.
The idea
Greedy algorithms make one decision per item and never revisit it. That only works if items come in a helpful order, which sorting provides.
The art is the sort key: intervals by end time to fit the most meetings, by start time to merge them, tasks by deadline, people by height.
See it step by step
Most meetings in one room: [[1, 3], [2, 5], [4, 6], [6, 8]]
- Sort by end: [1, 3], [2, 5], [4, 6], [6, 8]
- Take [1, 3] (free after 3). [2, 5] starts before 3: skip.
- Take [4, 6]. Take [6, 8]. → 3 meetings.
In code (Python)
def max_meetings(meetings):
meetings.sort(key=lambda m: m[1]) # earliest end first
count, free_at = 0, float("-inf")
for start, end in meetings:
if start >= free_at:
count += 1
free_at = end
return count
print(max_meetings([[1, 3], [2, 5], [4, 6], [6, 8]])) # 3O(n log n) for the sort, O(n) for the pass.
When you'll use it
- Meetings, intervals, arrows and balloons, assigning cookies, scheduling with deadlines.
Common mistakes
- Sorting by the wrong key (start when you need end, or the reverse).
- Not checking the greedy rule with a counterexample.
