Proving a greedy choice is safe

Before trusting a greedy strategy, argue it. Two techniques cover almost every case, and both are short enough to say aloud in an interview.

The exchange argument

Assume an optimal solution exists that differs from the greedy one. Show you can swap in the greedy choice without making the solution worse. If every difference can be exchanged away, the greedy solution is at least as good as the optimum — so it is optimal.

Interval scheduling — pick the most non-overlapping meetings:

Greedy takes the meeting that ends earliest. Suppose an optimal schedule starts with a different meeting. That meeting ends no earlier than the greedy one, so replacing it with the greedy choice leaves at least as much room for everything after. The count cannot fall. Repeat, and the greedy schedule matches the optimum.

function maxMeetings(intervals) {
  const sorted = [...intervals].sort((a, b) => a.end - b.end);   // earliest finish first
  let count = 0;
  let lastEnd = -Infinity;

  for (const { start, end } of sorted) {
    if (start >= lastEnd) { count++; lastEnd = end; }
  }

  return count;
}

Sorting by start time, or by shortest duration, both look reasonable and both are wrong. The proof is what tells them apart — not intuition.

Staying ahead

Show that after every step, the greedy solution is at least as good as any other on the metric that matters. Used for shortest paths and for problems like "minimum number of jumps".

Hunt for a counterexample first

Before proving anything, spend one minute trying to break it. Try:

• an element far larger than the others;
• ties everywhere;
• one item that only fits in the last position;
• an empty input, or a single element.

The coin system {25, 10, 1} from the last lesson is what a two-minute hunt produces. If you find a counterexample, you have saved yourself a wrong solution; if you cannot, you have material for the exchange argument.

In an interview

Say the strategy, then immediately justify it: "Sort by end time and take greedily — exchanging any other first choice for the earliest-ending one never reduces how many fit, so it is safe."

That sentence is worth more than the code. Interviewers ask greedy questions specifically to see whether you can distinguish "this seems reasonable" from "this is provably correct".