Exchange arguments

What is a greedy algorithm?

A greedy algorithm repeatedly makes a locally best choice and commits to it. It does not explore every combination or undo earlier choices. A greedy rule is correct only when you can explain why taking it still permits a globally best answer. A choice that looks best immediately can otherwise lead to a worse final result.

Example: To schedule the largest number of non-overlapping meetings, choose a meeting that finishes earliest, then repeat among meetings that start after it. Finishing early leaves as much room as possible for later meetings.

Helpful before this chapter

If these ideas are new, begin with:

Sorting and selection

Understand the idea

An exchange argument transforms an optimal solution to include the greedy choice without worsening it. Repeat on the remaining subproblem. Identify exactly which choice is exchanged and why feasibility survives.

Work through an example

Let O start with interval o; greedy g finishes no later. Replace o with g. Every later interval that followed o can still follow g, preserving count.

Time and space complexity

The proof establishes correctness; sorting still dominates O(n log n) runtime.

Why it works

After the exchange, at least one optimum shares the greedy prefix.

Common mistakes

An exchange must preserve all constraints.
A proof for unweighted count does not transfer to weighted reward.

Chapter lab · Python implementation

Greedy commits to a local choice without revisiting it. This requires a proof: a tempting rule can fail even on tiny inputs. Our lab selects the maximum number of nonoverlapping half-open intervals by earliest finishing time, then checks array reachability by maintaining the farthest reachable index.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def schedule(intervals):
    chosen=[]; end=float('-inf')
    for start,finish in sorted(intervals,key=lambda x:x[1]):
        if start>finish: raise ValueError('invalid interval')
        if start>=end:
            chosen.append((start,finish)); end=finish
    return chosen

def can_jump(values):
    if not values: return False
    if any(x<0 for x in values): raise ValueError('nonnegative jumps required')
    farthest=0
    for i,jump in enumerate(values):
        if i>farthest: return False
        farthest=max(farthest,i+jump)
        if farthest>=len(values)-1: return True
    return False

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert len(schedule([(1,4),(2,3),(3,5),(5,7)]))==3
assert can_jump([2,3,1,1,4])
assert not can_jump([3,2,1,0,4])
assert can_jump([0]) and not can_jump([])

CHECK YOUR UNDERSTANDING