Greedy Algorithms

The idea

A greedy algorithm builds the answer step by step, always taking the choice that looks best right now, and never reconsidering. It's usually simple and fast (often O(n log n) because of a sort) — but it's only correct for problems with the right structure.

When greedy works

Two properties:

1. Greedy choice property: some optimal solution starts with the greedy choice.
2. Optimal substructure: after making it, what remains is a smaller instance of the same problem.

Proving it: the exchange argument

Take any optimal solution that doesn't make the greedy choice. Show you can swap in the greedy choice without making it worse. Therefore an optimal solution with the greedy choice exists.

Example — activity selection (max non-overlapping intervals): pick the one that ends earliest. Let OPT's first interval be x, and greedy's be g with end(g) ≤ end(x). Replace x with g in OPT: g ends no later, so it can't conflict with anything that came after x. Same count, still valid. ∎

Family 1: Interval scheduling

Sort by end time; take an interval whenever it doesn't overlap the last one taken.

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

# Non-overlapping Intervals (min removals) = n - max_non_overlapping

int maxNonOverlapping(vector<vector<int>>& iv) {
    sort(iv.begin(), iv.end(), [](auto& a, auto& b) { return a[1] < b[1]; });
    int count = 0; long long lastEnd = LLONG_MIN;
    for (auto& x : iv)
        if (x[0] >= lastEnd) { count++; lastEnd = x[1]; }
    return count;
}

More in Intervals.

Family 2: Reachability (jump games)

Track the farthest point reachable so far.

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

def min_jumps(nums):                 # Jump Game II: implicit BFS levels
    jumps = cur_end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:             # must jump to go further
            jumps += 1
            cur_end = farthest
    return jumps

Family 3: Sort, then match

Sort both sides and pair them in a consistent order.

def find_content_children(greed, cookies):
    greed.sort(); cookies.sort()
    child = 0
    for c in cookies:
        if child < len(greed) and c >= greed[child]:
            child += 1
    return child

Two-sided greedy with pointers: Boats to Save People (heaviest with lightest), Bag of Tokens.

Family 4: Running balance with reset

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    tank = start = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:            # can't reach i+1 from any start in [start, i]
            start = i + 1
            tank = 0
    return start

Kadane's algorithm is the same idea: drop the running prefix when it goes negative.

Family 5: Two passes for two-sided constraints

Candy: each child with a higher rating than a neighbour gets more candy. Satisfy left neighbours in one pass, right neighbours in another, take the max.

def candy(ratings):
    n = len(ratings)
    c = [1] * n
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            c[i] = c[i - 1] + 1
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            c[i] = max(c[i], c[i + 1] + 1)
    return sum(c)

Family 6: Greedy + heap (“best available so far”)

When choices become available over time, keep them in a heap and take the best one when you must decide.

import heapq

def min_refuel_stops(target, fuel, stations):
    heap, stops, i = [], 0, 0          # max-heap of fuel amounts passed
    stations.append((target, 0))
    for pos, gas in stations:
        while fuel < pos:              # can't reach pos: refuel retroactively
            if not heap:
                return -1
            fuel += -heapq.heappop(heap)
            stops += 1
        heapq.heappush(heap, -gas)
    return stops

Same shape: IPO, Course Schedule III (take courses by deadline, drop the longest when over time), Furthest Building You Can Reach.

Family 7: Monotonic stack greedy

“Remove k digits to make the smallest number” — a smaller digit earlier always wins, so pop larger previous digits while you can.

def remove_k_digits(num, k):
    stack = []
    for d in num:
        while k and stack and stack[-1] > d:
            stack.pop()
            k -= 1
        stack.append(d)
    stack = stack[:len(stack) - k]        # still need to remove from the end
    return "".join(stack).lstrip("0") or "0"

Also: Remove Duplicate Letters, Create Maximum Number.

Family 8: Counting formulas

Task Scheduler: the most frequent task dictates the frame. With max frequency f and m tasks sharing it, the answer is max(len(tasks), (f − 1)(n + 1) + m).

Greedy vs DP: a quick test

Common mistakes

• Choosing the wrong sort key (start vs end, ascending vs descending).
• Not handling ties consistently (>= vs > for touching intervals).
• Assuming greedy works without testing a counterexample.
• Forgetting the feasibility pre-check (e.g. total gas < total cost).