Greedy Algorithms

Greedy algorithms make the best choice at each step, hoping it leads to the best overall solution. Sometimes it works perfectly, sometimes it doesn't. The trick is knowing when greedy is enough.

The Core Idea

At each decision point, pick the option that looks best right now. Don't look ahead, don't reconsider. Just grab the best thing available and move on.

Classic: Jump Game

Can you reach the last index if each element tells you max jump length?

def canJump(nums):
    max_reach = 0

    for i, jump in enumerate(nums):
        if i > max_reach:
            return False  # Can't reach here
        max_reach = max(max_reach, i + jump)

    return True

Classic: Activity Selection

Pick the maximum number of non-overlapping activities. Greedy: always pick the one that ends earliest.

def maxActivities(activities):
    # Sort by end time
    activities.sort(key=lambda x: x[1])

    count = 0
    last_end = 0

    for start, end in activities:
        if start >= last_end:
            count += 1
            last_end = end

    return count

Proving Greedy Works

If you need to prove it: show that the greedy choice is always part of some optimal solution, and that after making it, you have a smaller subproblem of the same type.