Advanced · Module 16 · Lesson 2 of 4

Exchange arguments

To prove a greedy order is optimal, take any solution that differs from it, swap two elements to make it more like the greedy one, and show the swap never makes it worse. Repeat until the two agree.

ProAbout 14 minutes

By the end you can

Prove a greedy ordering optimal with an adjacent-swap exchange argument
Derive a sorting key or comparator from what a swap changes
Recognize when an exchange makes things worse, which disproves a greedy rule

Builds on When greedy works.

01 · A question first

Five customers wait for one barber, needing 30, 10, 20, 5 and 15 minutes. Serving the shortest haircut first minimizes the total time customers spend in the shop. How can you be sure no clever order does better, without checking all 120 orders?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

Proving a greedy rule
Shortest job first
The swap tells you the sort key
When the exchange hurts
Exchange arguments without sorting
Writing the proof
Pseudocode & Multi-Language Implementations (C++, Java, Python)
Complexity Derivation, Edge Cases & Common Mistakes

See plans Already a member? Sign in

03 · Practice

Practice · medium · LeetCodeHand of straightsSplit a hand into groups of consecutive cards by always starting a group at the smallest remaining card.Practice · medium · LeetCodeMerge triplets to form target tripletDecide whether element-wise maximums of some triplets can equal a target, by merging only the triplets that never exceed it.Practice · medium · LeetCodeLargest numberArrange numbers so their concatenation is as large as possible, using a custom comparator that defines a valid total order.

Asked in interviews

Prove that serving the shortest job first minimizes total waiting time

Something wrong with this lesson? Report a problem