Greedy Algorithms

Which meeting do you keep?

Suppose a calendar contains these half-open intervals:

[0, 6)  [1, 4)  [3, 5)  [5, 7)  [5, 9)  [8, 9)

You want the largest possible set of non-overlapping meetings. The longest meeting is clearly unattractive, but that does not tell you what to choose. Earliest start takes [0, 6) and leaves room only for [8, 9). Shortest duration is no general remedy either: for [1, 4), [3, 5), and [4, 7), choosing the shortest middle interval produces one meeting where two were possible.

The safe choice is the compatible meeting that finishes first. Here it gives [1, 4), [5, 7), and [8, 9). The code is a sort and a scan. The difficult part is earning the right to discard every schedule that starts differently.

This is what separates greedy reasoning from a plausible heuristic. Backtracking keeps alternatives alive. Dynamic programming records the future consequences of different states. Greedy throws alternatives away because a proof says they are unnecessary. If the proof fails, the information that was discarded usually reappears as the state of a dynamic program—or as a small, embarrassing counterexample.

Exchange the first disagreement

Take an optimal interval schedule and call its first meeting o. Let g be the meeting with earliest finish time. If the optimal schedule already starts with g, there is nothing to show. Otherwise replace o with g.

Because g ends no later than o, every meeting that was compatible after o is still compatible after g. The replacement preserves the number of meetings. We have therefore produced an optimal schedule that begins with the greedy choice. What remains is the same problem on meetings that start after g finishes, so the argument can be repeated.

That is an exchange argument: find the first place an optimum differs from the proposed choice, make the exchange, and show that feasibility and value do not get worse. The proof does not claim that every optimal schedule begins with g; it establishes the weaker and sufficient fact that at least one does.

The implementation now follows from the proof:

sort intervals by end time
last_end = -infinity
selected = []

for interval in intervals:
  if interval.start >= last_end:
    selected.append(interval)
    last_end = interval.end

Sorting costs O(n log n) and the scan costs O(n). If the input is already ordered by finish time, the work is linear. Keeping only the count takes O(1) auxiliary space apart from the sort; returning the selected meetings requires space for the answer.

The compatibility convention belongs in the problem statement, not in a last-minute patch. Half-open intervals [1, 2) and [2, 3) do not overlap, so the comparison is start >= last_end. If touching endpoints conflict, it becomes start > last_end. Equal finish times do not affect the maximum count, though a deterministic secondary order makes the returned schedule easier to test.

A proof has four moving parts

Before calling an algorithm greedy, make four claims explicit:

1. Selection: which candidate is chosen next?
2. Feasibility: what makes that candidate legal?
3. Progress: what smaller problem remains after committing to it?
4. Safety: why can an optimal answer include the choice?

For interval selection, the answers are earliest finish, no overlap with the last selection, the suffix of compatible meetings, and the exchange above. The four claims travel together. “Sort the intervals” names a mechanism, not a selection rule. “It leaves more room” suggests the safety argument, but it does not yet show that replacing an optimal choice preserves every later meeting.

Exchange is not the only proof shape. Some algorithms maintain an invariant: a statement that is true before and after every iteration and is strong enough to imply the final answer. Others discard a dominated candidate and prove it can never become useful later. The common burden is the same: account for the future that an irreversible choice appears to ignore.

Try to break the rule before implementing it

Counterexample search is part of designing a greedy algorithm. Start with the smallest input that exposes the information a proposed rule discards.

The “largest coin first” rule fails for denominations [1, 3, 4] and amount 6: it returns 4 + 1 + 1, while 3 + 3 uses fewer coins. The rule happens to work for some coin systems, but the prompt did not grant that structure.

“Highest value first” fails for a knapsack of capacity 10 containing items (value 10, weight 10), (6, 5), and (6, 5). Taking the single highest value produces 10; taking the other two produces 12. Value density also fails for 0/1 knapsack: with capacity 50 and items (60, 10), (100, 20), and (120, 30), density order returns 160 while the last two items return 220.

These failures are diagnostic. Arbitrary coin change must remember the remaining amount. The knapsack choice must remember remaining capacity and which indivisible items remain. A local rule cannot erase those dimensions by being confidently stated.

A useful test is to attempt the exchange. If replacing the corresponding item in an optimum changes capacity, accumulated value, parity, category, cooldown, or path shape, ask whether the rest of the solution can still be repaired. If not, the missing fact belongs in a broader state model.

Resource allocation: count what must coexist

Now change the interval question. Every meeting must happen; the task is to find the minimum number of rooms. There is no schedule to select. The binding fact is simultaneous demand.

Sort meetings by start time and keep a min-heap of the end times of meetings currently occupying rooms. Before adding a meeting, remove every end time that is no later than its start. The largest heap size is the answer.

sort meetings by start time
active_end_times = min_heap()
max_rooms = 0

for meeting in meetings:
  while active_end_times not empty
        and active_end_times.min <= meeting.start:
    pop active_end_times

  push meeting.end into active_end_times
  max_rooms = max(max_rooms, active_end_times.size)

Immediately after a meeting starts, the heap contains exactly the meetings active at that time. Any allocation needs at least one room for each of those meetings. The construction uses exactly that many and releases rooms as soon as the boundary rule permits, so it reaches the lower bound.

The heap makes the invariant cheap to maintain; it is not the reason the algorithm is correct. If only the room count is needed, a sorted sweep over separate start and end events expresses the same lower-bound argument. If the prompt asks for room identities, the heap must retain them. The proof decides what the data structure needs to represent.

This distinction matters in more complicated resource-allocation prompts. A single heap works when future feasibility is captured by one ordered fact, such as earliest release time. Multiple resource types, compatibility classes, setup costs, or priorities may leave several dimensions alive. Using a heap does not make those dimensions disappear.

When history collapses to a frontier

Some greedy algorithms are justified by an invariant rather than an exchange. In jump-game reachability, scan the array while retaining only the farthest reachable index:

farthest = 0

for i in 0..n-1:
  if i > farthest:
    return false
  farthest = max(farthest, i + nums[i])

return true

Before each iteration, every useful index discovered so far lies in the reachable prefix ending at farthest. If i is beyond that boundary, no earlier position can reach it. Otherwise processing i can only extend the frontier. The exact path to an index is irrelevant because the prompt asks only whether the final index is reachable.

Change the prompt to ask for the number of paths and that compression is no longer valid. Two paths reaching the same frontier are now different answers. Change it to minimize a path-dependent cost and the cheapest route may matter. Greedy works here because the reachable set is a prefix and the requested answer depends only on its boundary.

This is the recurring shape behind prefix boundaries, active sets, monotonic stacks, and deficit resets: the proof shows that a compact summary contains all history the future can use. Each mechanism has its own question. Why is the useful set contiguous? Why can a popped item never recover? Why can an entire failed segment be rejected? Without that sentence, the data structure is only a hint.

The neighboring problem where greedy breaks

Give each meeting a weight and ask for a compatible schedule of maximum total weight. Earliest finish is no longer safe. Replacing the first interval in an optimum with an earlier-finishing interval may preserve every later meeting and still lose most of the value. The exchange preserved feasibility but not the objective.

Weighted interval scheduling usually sorts by finish time, finds the previous compatible interval for each meeting, and uses dynamic programming to compare taking and skipping. The state keeps the accumulated value that unweighted selection could ignore.

The same boundary separates fractional from 0/1 knapsack. With divisible items, a lower-density portion can be exchanged for a higher-density portion without violating capacity, so density order is safe. With indivisible items, the exchange may leave an unusable gap or displace a better combination.

Greedy is therefore not the family of “short solutions using sort, heap, or stack.” It is the family in which proof permits the future to be represented by one safe choice or compact invariant. Backtracking remains appropriate when distinct paths must be explored or enumerated. Dynamic programming is the natural next attempt when different choices lead to repeated states and the answer still depends on those states.

Make the proof visible in an interview

A strong explanation does not wait until after the code to mention why the rule works. For interval selection, it can be brief:

I will sort by finish time and repeatedly take the first compatible interval. If an optimal schedule starts with a later-finishing interval, I can replace that interval with the earliest-finishing one without excluding any later choice. That exchange preserves the count, so an optimum exists with my first choice, and the remaining suffix is the same problem.

Then state the endpoint convention, implement the scan, and analyze the sort. The explanation gives the interviewer something precise to challenge: the objective, the exchange, the compatibility boundary, or the complexity.

For a new prompt, work in this order:

1. State the objective and the scarce resource.
2. Propose the local choice and feasibility rule.
3. Construct a small counterexample for the most tempting competing rule.
4. Give an exchange argument, invariant, or dominance proof.
5. Only then choose the sort, heap, stack, scan, or counter that enforces it.

Practice in contrasting pairs: interval selection and weighted interval scheduling; fractional and 0/1 knapsack; jump reachability and path counting; canonical coin change and arbitrary denominations. The unsuccessful neighbor is often more instructive than another problem where the same trick works.

Before committing to greedy, ask one final question: what state would be needed if this local choice were unsafe? If the answer contains a meaningful dimension—capacity, value, previous category, remaining count, cooldown, or path—discard it only after a proof shows the future cannot observe it.

Related reading

• Chapter 31: Complexity and Constraint Analysis
• Chapter 43: Sorting, Searching, and Intervals
• Chapter 46: Recursion, Backtracking, and Divide and Conquer
• Chapter 48: Dynamic Programming