19 MIN GUIDE · INTERMEDIATE · GREEDY & INTERVALS

Greedy Algorithms and Interval Patterns

Know when a locally best choice is globally safe, prove it with an exchange argument, and master scheduling, merging and reachability patterns.

What makes an algorithm greedy?

A greedy algorithm commits to the best-looking choice available now and never revisits it. That is useful only when the problem has a greedy-choice property: some optimal solution begins with the greedy choice.

Dynamic programming compares several histories. Greedy reasoning proves that one history dominates the alternatives, so the others can be discarded.

Common proof styles are:

Exchange argument: replace the first non-greedy choice in an optimal solution with the greedy choice without making the solution worse.
Staying ahead: show that after every step, the greedy partial solution is at least as good as any competitor.
Cut property: show that the cheapest safe connection across a boundary belongs to some optimal structure, as in minimum spanning trees.

A rule is not correct merely because it works on examples. Search for a counterexample before trusting a greedy choice.

Interval vocabulary

An interval is usually represented as [start, end] or half-open [start, end). Decide whether touching endpoints overlap before writing comparisons.

Sorting reveals the structure:

Goal	Useful order	Greedy action
Detect or merge overlap	increasing start	compare with the latest merged end
Select most non-overlapping intervals	increasing end	take the next interval that starts after the last chosen end
Minimum rooms or platforms	starts and ends separately	advance the earlier event
Cover a target range	increasing start, farther end first	extend coverage as far as possible

Why earliest finish maximises activities

To attend the largest number of non-overlapping activities, choose the compatible activity that finishes earliest. Suppose an optimal schedule chooses a different first activity. Replacing it with the earlier-finishing greedy activity cannot block any later activity, so an equally large optimal schedule begins greedily. Repeat the argument for the remaining time.

Choose the maximum number of non-overlapping activities

Sort by finishing time
(1,2), (3,4), (0,6), (5,7), (5,9), (8,9)

Ends

246799

Earliest finish first

Finishing early leaves the most room for later choices.

Merging intervals

Sort by start. Keep one current merged interval:

if the next start is no greater than the current end, extend the current end,
otherwise the current interval is finished; append a new one.

Sorting makes this safe because no future interval starts earlier than the one being processed. A nested interval must not shorten the current end, so extend with the maximum of both ends.

Range expansion and jump problems

In minimum-jump problems, each jump count reaches a whole range of indices. Scan every index in the current range and track the farthest position reachable by one more jump. When the scan reaches the current boundary, commit the next jump and replace the boundary with that farthest reach.

This is breadth-first search over ranges, compressed into two integers. Choosing the index with the largest raw jump is not safe; the useful quantity is index + jump.

Activity selection implementation

def select_activities(intervals):
    chosen = []
    last_end = None
    for start, end in sorted(intervals, key=lambda item: (item[1], item[0])):
        if last_end is None or start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen


activities = [(1, 2), (3, 4), (0, 6), (5, 7), (5, 9), (8, 9)]
for start, end in select_activities(activities):
    print(start, end)

Output

Choosing between greedy and DP

Ask whether an early choice can be proved safe without knowing later choices. Weighted activity selection is a warning: choosing the earliest finish may maximise the number of activities but not their total value. When alternatives must be compared because a locally weaker choice can enable a larger future reward, dynamic programming is usually needed.

Practice overlap detection in Can Attend Every Meeting?, merging in Merge Overlapping Intervals, and range expansion in Minimum Jumps to the End.