When does a greedy choice work?

Greedy choices and intervals Mid-level Python 3.13+ Reviewed By Best Latest Apps

Pick the fix

Your greedy rule for picking non-clashing bookings sorts by length (shortest first). Which input breaks it?

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [1, 5), [4, 7), [6, 10): the shortest one blocks both others

Right: earliest end keeps two, shortest-first keeps one.

One counterexample is enough to reject a greedy rule, which is why testing tiny cases is part of the method.

Why not the others?
  • B [1, 2), [3, 4), [5, 6): no clashes at all. Every rule keeps all three here.
  • C A single booking. One booking is trivial for any rule.

30-second answer

A greedy algorithm makes the locally best choice and never revisits it. It is correct when you can show an exchange argument: take any optimal answer, swap its first choice for the greedy one, and show the result is still optimal. Then repeat. If a small counterexample breaks the rule, use DP instead.

Practise saying it · 45 s. No recording, just a timer

Explain how you justify a greedy rule.

Say your answer out loud, then check which of these points you covered:

  • Exchange argument
  • Test tiny cases
  • Fall back to DP

Deep dive

Try three or four tiny inputs against brute force before trusting a greedy rule.

Sorting by the right key is often the whole greedy idea.

Coin systems show the risk: greedy works for 1, 5, 10, 25 but not for 1, 3, 4.

Common mistakes

  • Presenting a greedy rule without any argument.
  • Assuming a rule that works on the examples works in general.

Senior take & follow-ups

Say 'here is why this choice is safe' before writing greedy code.

Follow-up questions

Think of your answer first, then open the hint.

  1. What is an exchange argument?

    Show hint

    Show any optimal answer can be changed step by step into the greedy one without getting worse.

  2. What if you cannot prove it in time?

    Show hint

    Say so, test with brute force, and offer the DP as a safe alternative.

What each operation costs: Merge Sort · Quick Sort

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.