Greedy Algorithms — When the Best Local Choice Wins

A greedy algorithm builds the answer by always making the choice that looks best right now, never reconsidering. When it works, it's usually the simplest and fastest solution — often O(n) or O(n log n). The hard part is knowing when it works.

Greedy vs dynamic programming

• DP considers every choice and combines the best results of subproblems.
• Greedy commits to one choice per step.

Greedy is correct only when a locally best choice can always be extended to a globally best answer. A quick check: try to find a counter-example. For coin change with [1, 3, 4] and amount 6, "take the biggest coin" gives 4+1+1 = 3 coins, but 3+3 = 2 coins — so greedy fails and you need DP.

In interviews, briefly justify greedy with an exchange argument: "if an optimal answer made a different choice here, swapping it for our choice doesn't make it worse."

Pattern 1 — Sort, then pick (Assign Cookies)

Each child needs a cookie of at least their greed size. Maximise happy children. Sort both; give the smallest cookie that satisfies the least greedy child:

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

Using the smallest sufficient cookie keeps bigger cookies for greedier children — that's the exchange argument.

Pattern 2 — Intervals: sort by end time

Non-overlapping Intervals: remove the fewest intervals so the rest don't overlap. Sort by end time and keep each interval that starts after the last kept one ends. Finishing early leaves the most room for the rest.

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])
    removed, last_end = 0, float('-inf')
    for start, end in intervals:
        if start >= last_end:
            last_end = end          # keep it
        else:
            removed += 1            # overlaps → remove
    return removed

int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
    int removed = 0; long lastEnd = Long.MIN_VALUE;
    for (int[] iv : intervals) {
        if (iv[0] >= lastEnd) lastEnd = iv[1];
        else removed++;
    }
    return removed;
}

This is the classic activity selection problem.

Pattern 3 — Track the farthest reach (Jump Game)

Each nums[i] is the max jump from index i. Can you reach the end? Keep the farthest index reachable so far:

def can_jump(nums):
    farthest = 0
    for i, jump in enumerate(nums):
        if i > farthest:
            return False            # stuck before reaching i
        farthest = max(farthest, i + jump)
    return True

Jump Game II (minimum jumps) uses the same idea in "levels": the current jump covers [start, end]; the next jump can reach up to the farthest point from that range — like BFS without a queue.

def jump(nums):
    jumps = end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == end:                # used up the current jump's range
            jumps += 1
            end = farthest
    return jumps

Pattern 4 — Running balance (Gas Station)

If the total gas ≥ total cost, a solution exists. Walk the stations keeping a running tank; whenever it drops below zero, no station from the current start up to here can work — start again from the next station.

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:
            start, tank = i + 1, 0
    return start

Pattern 5 — Last occurrence (Partition Labels)

Split a string into as many parts as possible so each letter appears in only one part. Record each letter's last index; extend the current part until you reach the farthest last index of the letters inside it.

def partition_labels(s):
    last = {ch: i for i, ch in enumerate(s)}
    res, start, end = [], 0, 0
    for i, ch in enumerate(s):
        end = max(end, last[ch])
        if i == end:
            res.append(end - start + 1)
            start = i + 1
    return res

How to recognise greedy

• Intervals, scheduling, meetings → sort by end (or start) and sweep.
• "Minimum number of …", "maximum number of …" where a simple rule seems to work and you can't find a counter-example.
• Reachability with a "farthest so far" variable.

Common mistakes

1. Using greedy without checking a counter-example (coin change!).
2. Sorting intervals by the wrong key (start vs end changes the answer).
3. Off-by-one in Jump Game II's loop (stop at n − 2).

Key takeaways

• Greedy = best local choice, never undone. Fast and simple when it's provably right.
• Justify with an exchange argument; disprove with a counter-example.
• Core patterns: sort then pick, intervals by end time, farthest reach, running balance, last occurrence.