Greedy Algorithms

A greedy algorithm makes the locally optimal choice at each step, hoping to find a global optimum.

Real-World Analogy

You're at a vending machine with coins. You need to give someone 41 cents. What do you do?

• Greedy: Use the largest coin possible each time
  • 25 cents (remaining: 16)
  • 10 cents (remaining: 6)
  • 5 cents (remaining: 1)
  • 1 cent (remaining: 0)
  • Total: 4 coins

This works because US coins have the right properties. But it doesn't always work — see the counterexample below.

When Greedy Works

Greedy works when the problem has two properties:

1. Greedy Choice Property: A locally optimal choice leads to a globally optimal solution
2. Optimal Substructure: An optimal solution contains optimal solutions to subproblems

When Greedy Fails

Counterexample: Coin Change

Coins: [1, 3, 4], Target: 6

• Greedy: 4 + 1 + 1 = 6 (3 coins)
• Optimal: 3 + 3 = 6 (2 coins)

Greedy fails because the coin system doesn't have the greedy choice property.

Greedy vs DP

How to Identify Greedy Problems

Signals:

• "Maximum" or "Minimum" in the question
• "Fewest" or "Most" number of items
• "Can you..." (yes/no with optimal strategy)
• Interval scheduling
• Assignment problems

Keywords:

• "At each step"
• "Choose the best"
• "Optimal"

Common Greedy Patterns

1. Sorting: Sort by some criteria, process in order
2. Priority Queue: Always pick the best element
3. Interval Scheduling: Sort by end time, pick non-overlapping
4. Huffman-like: Combine smallest two repeatedly

Greedy Proof (Exchange Argument)

To prove greedy is optimal:

1. Assume there's a better solution B
2. Find the first place B differs from greedy G
3. Show swapping makes B no worse than G
4. This contradicts B being better

This proves greedy is at least as good as any other solution.

Pattern 1: Sort and Scan

Sort by some criteria, then make greedy choices.

// Activity Selection: maximum non-overlapping activities
public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);  // Sort by end time
    int count = 0;
    int lastEnd = intervals[0][1];
    
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= lastEnd) {
            count++;  // No overlap, keep it
            lastEnd = intervals[i][1];
        }
    }
    return intervals.length - count;  // Remove minimum
}

Pattern 2: Priority Queue (Heap)

Always pick the best element.

// Task Scheduler: minimum intervals with cooldown
public int leastInterval(char[] tasks, int n) {
    int[] count = new int[26];
    for (char c : tasks) count[c - 'A']++;
    
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    for (int c : count) {
        if (c > 0) pq.offer(c);
    }
    
    int intervals = 0;
    while (!pq.isEmpty()) {
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            if (!pq.isEmpty()) {
                temp.add(pq.poll() - 1);
            }
        }
        for (int t : temp) {
            if (t > 0) pq.offer(t);
        }
        intervals += pq.isEmpty() ? temp.size() : n + 1;
    }
    return intervals;
}

Pattern 3: Interval Scheduling

Sort by end time, pick greedily.

// Maximum meetings in one room
public int maxMeetings(int[] start, int[] end) {
    int n = start.length;
    int[][] meetings = new int[n][2];
    for (int i = 0; i < n; i++) {
        meetings[i][0] = start[i];
        meetings[i][1] = end[i];
    }
    
    Arrays.sort(meetings, (a, b) -> a[1] - b[1]);
    
    int count = 1;
    int lastEnd = meetings[0][1];
    for (int i = 1; i < n; i++) {
        if (meetings[i][0] > lastEnd) {
            count++;
            lastEnd = meetings[i][1];
        }
    }
    return count;
}

Pattern 4: Jump Game

Track the farthest reachable position.

public boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}

Pattern Selection Guide

Interval problems are a classic greedy category.

Interval Sorting

Always sort intervals first. The sorting criterion determines the greedy strategy.

Merge Intervals

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> merged = new ArrayList<>();
    
    for (int[] interval : intervals) {
        if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
            merged.add(interval);
        } else {
            merged.get(merged.size() - 1)[1] = Math.max(
                merged.get(merged.size() - 1)[1], interval[1]);
        }
    }
    return merged.toArray(new int[0][]);
}

Non-overlapping Intervals

public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    int count = 0;
    int lastEnd = intervals[0][1];
    
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= lastEnd) {
            lastEnd = intervals[i][1];
        } else {
            count++;  // Must remove this interval
        }
    }
    return count;
}

Insert Interval

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0;
    
    // Add all intervals before newInterval
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i++]);
    }
    
    // Merge overlapping intervals
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.add(newInterval);
    
    // Add remaining intervals
    while (i < intervals.length) {
        result.add(intervals[i++]);
    }
    
    return result.toArray(new int[0][]);
}

Meeting Rooms II (Minimum rooms needed)

public int minMeetingRooms(int[][] intervals) {
    if (intervals.length == 0) return 0;
    
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    pq.offer(intervals[0][1]);
    
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= pq.peek()) {
            pq.poll();  // Reuse room
        }
        pq.offer(intervals[i][1]);
    }
    return pq.size();
}

When Interval Greedy Works

• Merge Intervals: Sort by start, merge overlapping
• Non-overlapping: Sort by end, pick greedily
• Minimum removals: Convert to non-overlapping problem
• Maximum meetings: Sort by end, pick greedily

Time Complexity

Proving Greedy Correctness

Method 1: Exchange Argument

1. Assume optimal solution O differs from greedy G
2. Find first position where they differ
3. Show swapping makes O no better than G
4. Contradiction: O was optimal

Method 2: Greedy Stays Ahead

1. Define a metric that greedy maximizes
2. Show greedy is always ahead at each step
3. Therefore greedy is optimal

Method 3: Matroid Theory

• If the problem forms a matroid, greedy is optimal
• Examples: MST, activity selection

Common Greedy Pitfalls

1. Assuming greedy always works: Must prove it!
2. Wrong sorting criterion: Different sorts give different results
3. Missing edge cases: Empty input, single element
4. Overflow: When computing sums or products

Greedy vs DP Decision Tree

Is there optimal substructure?
├── No → Not solvable optimally
└── Yes
    ├── Are overlapping subproblems present?
    │   ├── Yes → Use Dynamic Programming
    │   └── No
    │       ├── Can you prove greedy choice property?
    │       │   ├── Yes → Use Greedy
    │       │   └── No → Use DP or Backtracking
    │       └── Is speed critical?
    │           ├── Yes → Try Greedy first
    │           └── No → Either works

Greedy Problem Checklist

• Can you define a local choice?
• Does the choice lead to global optimum?
• Can you prove correctness?
• What's the sorting criterion?
• Edge cases handled?