223: Greedy Algorithms: Exchange Arguments, Interval Scheduling, and Local Choices

Learning outcomes

By the end of this lesson, you should be able to:

explain and apply the greedy-choice property in a realistic implementation;
explain and apply an exchange argument in a realistic implementation;
explain and apply interval scheduling in a realistic implementation;
explain why sorting is often setup for a greedy algorithm and use it appropriately;
use counterexamples to test whether a plausible greedy rule is actually safe.

These are reasoning skills, not recipes to memorize. The goal is to recognize when an irreversible local choice is justified, implement that choice with a clear invariant, and know when the proof does not apply.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where you had to choose between a simple local rule and a more explicit comparison of alternatives. It might have involved scheduling work, selecting records, prioritizing a queue, or processing data in order.

That retrieval is useful because the same question appears in both an interview-sized problem and production data processing: can you commit to the next choice without losing the best possible result? The point is not to memorize the word greedy. Start from the constraints, state what must remain true, and then decide whether the local rule has a defensible proof.

Terminology

Greedy-choice property: A locally optimal choice can be part of at least one global optimum. The wording matters: the property does not claim that every locally optimal choice works, and it does not apply to every optimization problem.
Exchange argument: Begin with an optimal solution and compare it with the greedy solution. If their first choices differ, exchange the optimal solution's choice for the greedy choice without making the result worse. Repeat this reasoning for the remaining input.
Interval scheduling: When the objective is to select as many mutually compatible intervals as possible, repeatedly selecting the compatible interval with the earliest finish time is optimal. Earliest start time and shortest duration do not generally provide the same guarantee.
Sorting as setup: Many greedy algorithms first sort the input by a carefully chosen key. The scan may then be O(n), but the complete algorithm is usually O(n log n) because of the sort.
Counterexamples: Before trusting a greedy rule, search small inputs for a case where it produces a worse answer than another valid choice. A small counterexample can disprove a rule quickly.
Greedy versus DP: If a local choice changes future possibilities in a way that an exchange proof cannot neutralize, dynamic programming may be needed to compare alternative states instead of committing immediately.

The useful distinction is between a rule that merely looks sensible and one whose choice can be proved safe. Sorting, scanning, and getting a plausible answer are implementation details; the proof is what establishes correctness.

Mental model

Treat Greedy Algorithms: Exchange Arguments, Interval Scheduling, and Local Choices as a design problem with observable inputs, outputs, invariants, and failure modes. A greedy algorithm makes an irreversible local decision. Once an item is accepted, an interval is scheduled, or a denomination is selected, the algorithm does not revisit that decision. That commitment is efficient when the problem has the right structure, but dangerous when an early choice can block a better combination later.

Correctness therefore requires more than the intuition that a choice “seems best.” Use a proof such as an exchange argument, a staying-ahead argument, a cut property, or a matroid-like structure when it fits the problem. A strong implementation makes assumptions visible, narrows uncertainty at boundaries, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to explain why the design is safe.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call or a sorting comparator. First state the objective and what must remain true after each choice. Then choose the mechanism that enforces that invariant. If you cannot explain why the next local choice preserves the possibility of an optimum, you have a hypothesis to test, not a finished algorithm.

Deep dive

1. Greedy-choice property

Many optimization problems ask you to maximize or minimize a result while making choices from a set of candidates. The tempting approach is to choose what looks best right now. Sometimes that is exactly right; sometimes the choice consumes a resource or blocks a combination that would have been better overall.

The greedy-choice property says that a locally optimal choice can belong to some global optimum for the specific problem. “Can belong” is deliberately weaker than “is the only correct choice.” Several choices may tie, but at least one optimal solution remains available after the greedy choice. This property must be established for the problem rather than assumed from the shape of the input.

Decision rule: Use the greedy-choice property deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption about the data, prefer the more explicit design. In practice, write down the objective, the candidate ordering, and the fact that remains true after the choice; those statements expose whether the rule is actually justified.

2. Exchange argument

An exchange argument is a way to turn that intuition into a proof. Take an optimal solution, compare its first differing choice with the greedy choice, and exchange the optimal solution's choice for the greedy one. If the exchange keeps the solution valid and does not reduce its quality, there is still an optimal solution beginning with the greedy choice. Apply the same reasoning to the remaining problem.

For interval scheduling, for example, the greedy choice is the compatible interval that finishes earliest. If an optimal schedule starts with a different compatible interval, replacing that first interval with the earlier-finishing one leaves at least as much room for every later interval. The replacement does not reduce the number of intervals that can be scheduled. This is the key argument; “earlier seems better” by itself is not.

Decision rule: Use an exchange argument deliberately when it makes the contract or invariant easier to prove. If you cannot show that the exchange preserves feasibility and objective value, do not present the algorithm as correct. A brute-force comparison on small cases can help find a counterexample, but testing cannot replace the proof for all valid inputs.

3. Interval scheduling

In interval scheduling, each item has a start and finish time, and the goal is to select the largest possible set of non-overlapping intervals. The optimal rule is to sort by finish time and repeatedly take the next interval whose start is at least the finish time of the last selected interval.

The invariant is straightforward: after each selection, the chosen intervals are compatible, and the last selected interval finishes as early as possible among schedules with the same number of selections considered so far. Finishing earlier leaves more room for future intervals. This is why earliest finish time works, while earliest start time or shortest duration does not generally have the same guarantee.

Decision rule: Use interval scheduling deliberately when the objective is the number of compatible intervals and the compatibility rule is the stated one. If intervals have weights, priorities, or other value, this is a different problem; the unweighted earliest-finish proof no longer automatically applies.

4. Sorting as setup

Sorting often makes the greedy invariant visible. Once intervals are ordered by finish time, a single forward scan can discard intervals that conflict with the current selection and accept the next compatible one. The scan is O(n), but sorting dominates the total running time, which is O(n log n) for a comparison sort.

The sort key is part of the algorithm, not a cosmetic preprocessing step. Sorting by the wrong field can preserve a fast implementation while destroying correctness. Also account for storage: an in-place sort may use different auxiliary space from a copied or immutable representation, and the input's mutability may be part of the API contract.

Decision rule: Use sorting as setup deliberately when the ordering exposes a proof-friendly invariant. Document the key, tie behavior, and mutation expectations. If the input is already sorted or the key has a bounded structure that supports a cheaper arrangement, revisit the complexity rather than automatically paying for a general-purpose sort.

5. Counterexamples

Before trusting a greedy rule, try to break it with small inputs. Coin change with arbitrary denominations is the classic warning: choosing the largest denomination first can fail. With denominations [1, 3, 4] and target 6, largest-first chooses 4, then 1, then 1, using three coins. The better answer is 3 + 3, using two.

The failure is not that the implementation scanned incorrectly. The rule itself lacks the property needed to make each local choice safe for arbitrary denominations. Some denomination systems do support a largest-first strategy, but that requires an appropriate guarantee; it cannot be inferred merely because the denominations are positive or sorted.

Decision rule: Use counterexamples deliberately when a greedy rule feels obvious but has not been proved. Generate or inspect small adversarial inputs, compare against brute force where feasible, and record the missing property. A counterexample is also a useful debugging artifact because it states the smallest boundary at which the proposed invariant becomes false.

6. Greedy versus DP

Greedy and dynamic programming solve different kinds of uncertainty. Greedy commits to one choice because a proof shows that commitment is safe. Dynamic programming keeps enough alternative states to compare futures when an early choice can materially change what remains possible.

If local choices affect future possibilities in a way an exchange proof cannot neutralize, dynamic programming may be needed. Weighted interval scheduling is a useful contrast with unweighted interval scheduling: an interval that finishes earliest may have low value, so the algorithm must compare taking it with skipping it in favor of a more valuable compatible combination.

Decision rule: Use greedy versus DP deliberately when it makes the contract or invariant easier to prove. If the objective includes weights, capacities, dependencies, or a future benefit that the local key cannot represent, first look for a state definition and recurrence. Do not force a greedy solution merely because it is shorter.

Worked example

Consider both an interview-sized problem and a production data-processing problem. In either setting, start by writing the requirement in one sentence, list the input and output contracts, and identify which concept owns each failure mode. For interval scheduling, a precise requirement might be: “Given valid intervals, return a maximum-cardinality set of pairwise non-overlapping intervals, using the chosen boundary convention.” That last clause matters: whether an interval ending at time t may be followed by one starting at t is part of the contract.

The important design move is separation. Parsing and validation belong at the boundary; domain rules belong in the domain or service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns can make a happy-path demo look shorter, but it makes edge cases, retries, and debugging much harder to reason about.

The small function below is not an interval-scheduling solution. It is a deliberately simple example of stating an invariant before choosing the data structure and implementing a scan whose state is easy to inspect:

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

Here, answer is the greatest value seen so far, so the invariant is maintained after every iteration. The function also reveals a contract question: returning 0 for an empty input is only correct if zero is the specified identity or default. If an empty collection should be rejected, the boundary must validate it instead. A production implementation should also decide how to handle non-finite numbers if those are not valid domain values.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For this pure function, retries and dependency failures do not apply directly; say that explicitly rather than inventing behavior. In a data-processing service, identify which layer detects malformed input, duplicate work, or a failed dependency, and state what the caller observes. That level of contract reasoning is what a senior code review or technical interview is testing.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. A mathematically correct greedy algorithm can still fail operationally if unvalidated records violate its assumptions, if a sort consumes unbounded memory, or if a retry duplicates an output.

Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence. For a large interval stream, consider whether all data must be materialized before sorting, whether the source can provide the required order, and how ties and malformed intervals are reported. Those are deployment and data-contract decisions, not changes to the exchange proof.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and every network input is untrusted.

Guided lab

Prove and implement interval scheduling, then test a naive greedy rule for coin change or knapsack and find a counterexample. Explain which missing property causes the greedy rule to fail. For interval scheduling, include the sort key, the compatibility condition, the invariant, and the resulting time and space complexity. For the failed rule, compare its result with an exhaustive or otherwise trusted solution on small inputs.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

The lab is complete only when you can explain both outcomes: why earliest finish time is safe for the stated interval objective, and why the tested coin-change or knapsack rule is not safe without an additional property.

Edge cases and failure modes

Greedy-choice property: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Also test cases where several candidates tie, because tie handling can expose an unstated assumption.
Exchange argument: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Check that the proposed exchange preserves both feasibility and the objective.
Interval scheduling: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include empty input, one interval, touching endpoints, nested intervals, equal finish times, and intervals with invalid start or finish values.
Sorting as setup: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify the comparator, tie behavior, input mutation, and memory use.
Counterexamples: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Preserve the smallest failing case so a future change cannot accidentally hide the reason the rule was rejected.

Boundary conventions deserve an explicit test. If [start, finish) intervals are used, an interval starting exactly when the previous one finishes is compatible. If endpoints are closed, it is not. Neither convention is universally correct; silently switching between them is the bug.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.
Treating a plausible local rule as proof of correctness, or sorting by a convenient field without checking that the field supports the exchange argument.

For debugging, reproduce the smallest failing case, inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. For a greedy algorithm, log or inspect the ordered candidates, the state before each choice, the choice made, and the remaining feasible options. If the result is wrong, determine whether the input violated the contract, the comparator was wrong, the compatibility boundary was wrong, or the greedy property never held.

Interview questions

What problem does Greedy-choice property solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Exchange argument solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Interval scheduling solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Sorting as setup solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Counterexamples solve, and what trade-off or failure mode would make you choose a different approach?

When answering, do not stop at a definition. State the objective, the invariant or proof idea, the complexity, and one case where the approach fails or requires a different model.

Checkpoint

Without notes, explain Greedy Algorithms: Exchange Arguments, Interval Scheduling, and Local Choices to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.