Counterexamples

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

Search for the smallest counterexample before trusting a local heuristic. Vary one feature at a time: equal values, one dominating option, a misleading early choice, or a delayed payoff.

Work through an example

Choosing earliest start picks [0,10) and blocks [1,2),[2,3),[3,4), giving one instead of three. Shortest-duration rules can also block two compatible intervals.

Time and space complexity

Tiny exhaustive enumeration can compare a heuristic against brute force; its cost is exponential in test size.

Why it works

One valid counterexample disproves a universal correctness claim.

Common mistakes

Passing random tests is not a proof.
Counterexamples must satisfy the original input contract.

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