Greedy Algorithms: Proof Methods and Counter-example Analysis

Core Philosophy

A Greedy Algorithm builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. It never reconsiders choices made in the past.

[!IMPORTANT] Greedy is not always correct! To use it, you must satisfy the Greedy Choice Property (a local optimum is part of a global optimum) and ensure the problem has Optimal Substructure.

Greedy vs. Dynamic Programming

How to Prove a Greedy Strategy

Method 1: Exchange Argument

Assume there is an optimal solution $OPT$ that differs from the greedy selection at some step. Show that by "exchanging" the $OPT$ choice with the greedy choice, the solution does not worsen. By repeating this, any optimal solution can be transformed into the greedy one.

Method 2: Induction

Greedily process elements one by one. Prove via induction that after $k$ steps, the greedy prefix is part of some global optimal solution.

Method 3: Direct Counter-example

If a greedy idea is wrong, you only need to produce one single scenario where it yields a sub-optimal result to dismiss it.

Classic: Interval Scheduling

Goal: Given $N$ intervals, pick the largest possible set of non-overlapping intervals.

• Faulty Idea 1: Pick the earliest start $\to$ Counter: [1, 10], [2, 3] (picking the first blocks the second).
• Faulty Idea 2: Pick the shortest $\to$ Counter: [1, 5], [4, 6], [5, 10] (picking the short middle one blocks two long ones).
• Correct Strategy: Pick the interval that ends earliest. This leaves maximum room for all subsequent intervals.

public int eraseOverlapIntervals(int[][] intervals) {
    // Sort by END time
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
    int count = 0, currentEnd = Integer.MIN_VALUE;
    for (int[] range : intervals) {
        if (range[0] >= currentEnd) {
            count++;
            currentEnd = range[1];
        }
    }
    return count;
}

Classic: Jump Game (Farthest Reach)

// LeetCode 55 - Can Reach Last Index?
public boolean canJump(int[] nums) {
    int farthest = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > farthest) return false; // This index is unreachable
        farthest = Math.max(farthest, i + nums[i]);
    }
    return true;
}

// LeetCode 45 - Minimum Jumps?
public int jump(int[] nums) {
    int jumps = 0, currentEndOfJump = 0, farthestNext = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        farthestNext = Math.max(farthestNext, i + nums[i]);
        if (i == currentEndOfJump) {
            jumps++;
            currentEndOfJump = farthestNext;
        }
    }
    return jumps;
}

Multidirectional Greedy: Candy (LeetCode 135)

Requirement: Neighbors with higher ratings get more candy.

Strategy: Solve from two directions.

1. Left-to-Right: If $R[i] > R[i-1]$, give 1 more than neighbor.
2. Right-to-Left: If $R[i] > R[i+1]$, ensure current is at least 1 more than the right neighbor.

public int candy(int[] ratings) {
    int n = ratings.length;
    int[] out = new int[n];
    Arrays.fill(out, 1);
    for (int i = 1; i < n; i++)
        if (ratings[i] > ratings[i-1]) out[i] = out[i-1] + 1;
    for (int i = n-2; i >= 0; i--)
        if (ratings[i] > ratings[i+1]) out[i] = Math.max(out[i], out[i+1] + 1);
    return Arrays.stream(out).sum();
}

Common Greedy Paradigms

Failure Case Example: Coin Change

Requirement: Smallest number of coins for sum $X$. Deniminations [1, 5, 6], Target 10.

• Greedy: Pick 6 $\to$ remains 4 $\to$ four 1s. Total 5 coins.
• Optimal: Pick two 5s. Total 2 coins.

Conclusion: Greedy doesn't always handle change. Use Dynamic Programming for universal coin problems. 筋