Sort First, Greedy Second — Scheduling and Packing

Many greedy algorithms become obvious after you sort. The sort exposes structure—earliest finishing meetings, cheapest edges, longest jobs first for lateness—so the greedy rule is just a linear scan afterward.

Why this shows up in the real world

Class photo scheduling: sort children by height before assigning rows so you never backtrack. Airline boarding groups passengers by zone and seat order to minimize aisle blocking—sort keys encode policy. CPU scheduling often sorts tasks by deadline (Earliest Due Date first) when a greedy is optimal under assumptions. The pattern: sort to reveal priority, then one pass to commit decisions.

Core idea (explained for students)

Identify a score or tuple key that makes the greedy choice locally obvious if items are processed in sorted order. Prove (or sanity-check) exchange argument: swapping an inversion against sorted order cannot improve the objective. Implement: items.sort(key=...) then accumulate answer with O(n) or O(n log n) follow-up. Watch stability if ties carry hidden constraints.

Try this in Python

# Classic interval scheduling after sorting by end time
intervals = [(1, 3), (2, 5), (4, 6), (0, 2)]
intervals.sort(key=lambda x: x[1])
end = -1
picked = []
for s, e in intervals:
    if s >= end:
        picked.append((s, e))
        end = e
print(picked)

Common mistakes

• Sorting by the wrong key—objective looks greedy but is not.
• Assuming sort order equals execution order when constraints are dynamic.
• O(n log n) sort dominating when an O(n) counting trick exists.

Key takeaways

• Sort + scan is a standard interview template.
• Always ask: what breaks the greedy after sorting?
• Pair with proof sketches in comments for future you.