Greedy

Greedy Algorithms

At each step, pick the locally best choice and never look back. Works when local optimal = global optimal.

Jump Game — Greedy Reach Tracking

Each cell = max jump length. Greedily track max reachable index. If current > max_reach, we're stuck!

max_reach: 0
Press Animate to start.
Merge Intervals — Sort + Greedily Merge
Press Animate to see interval merging.

When Greedy Works vs Doesn't

Greedy works when...
Making the locally best choice at each step never prevents a globally optimal solution. Prove it with the "exchange argument": swapping greedy choice for any other never improves the result.
Greedy WorksUse DP Instead
Activity selection (end time)0/1 Knapsack
Interval mergingSubset sum
Fractional KnapsackLongest path in graph
Jump Game IEdit distance
Minimum spanning treeMatrix chain multiplication
Quick test
Try greedy, then test with a small counterexample. If counterexample exists → use DP. If greedy always matches the optimal → you're good.

Greedy = Sort First, Then Pick

Common Signal
If the problem says "minimum number of X", "maximum number of Y without conflict", or "earliest finish time" — try sorting by the key constraint, then greedily pick.

Jump Game + Merge Intervals

# Jump Game — track max reachable
def can_jump(nums):
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach: return False  # stuck!
        max_reach = max(max_reach, i + jump)
    return True

# Merge Intervals — sort by start
def merge(intervals):
    intervals.sort()
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:  # overlaps
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

# Gas Station — circular greedy
def can_complete_circuit(gas, cost):
    total = cur = start = 0
    for i in range(len(gas)):
        diff = gas[i] - cost[i]
        total += diff; cur += diff
        if cur < 0: start = i + 1; cur = 0
    return start if total >= 0 else -1

LeetCode Problems

  • MediumJump GameTrack max reachable
  • MediumJump Game IICount jumps greedily
  • MediumMerge IntervalsSort by start + merge
  • MediumNon-overlapping IntervalsSort by end + skip overlaps
  • MediumGas StationCircular greedy
  • MediumTask SchedulerMost frequent task first
  • HardCandyTwo-pass greedy