Local choices and global goals

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

A greedy choice must preserve some globally optimal solution. Separate the objective from the local rule: choosing a large immediate reward may block better future combinations.

Work through an example

For maximum interval count, choose the earliest finish, not earliest start or shortest duration. Finishing early leaves the widest remaining time range.

Time and space complexity

Sorting O(n log n), selection O(n); output O(n).

Why it works

There exists an optimal solution beginning with the greedy chosen interval.

Common mistakes

A plausible rule is not a proof.
Weighted interval reward requires DP rather than this count-based greedy rule.

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