Reachability choices

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

Reachability greedy keeps an aggregate frontier instead of choosing a fixed jump too early. Every reachable index can extend the farthest boundary. Minimum-jump variants process reachable layers, similar to BFS.

Work through an example

[2,3,1,1,4] reaches index 2 from zero; visiting index 1 extends reach to 4. Always taking the largest immediate landing value is a different and potentially wrong rule.

Time and space complexity

O(n) time/O(1) auxiliary state.

Why it works

Every index up to farthest is reachable under the nonnegative jump model.

Common mistakes

An index beyond farthest is not available for extension.
Empty input needs a defined 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