Greedy Algorithms

Concept

A greedy algorithm makes the locally best choice and never reconsiders. It is fast but only correct when the problem has the greedy-choice property.

Interval problems are classic: sort by end time and pick non-overlapping intervals.

If a counter-example breaks greedy (like coin change with coins 1, 3, 4 for amount 6), switch to DP.

Complexity

Code (Python)

def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])
    count, end = 0, float("-inf")
    for s, e in intervals:
        if s >= end:
            count += 1
            end = e
    return count

def can_jump(nums):
    reach = 0
    for i, x in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + x)
    return True

Remember

• Sort first — most greedy solutions start with sorting.
• Try to find a counter-example before trusting greedy.
• Intervals → sort by start or end.