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

Aspect	Greedy	DP
Approach	Local optimal	All subproblems
Speed	Usually O(n log n)	Usually O(n²) or O(n)
Correctness	Must prove	Always correct
When to use	Greedy choice property holds	Optimal substructure + overlapping subproblems

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

Pattern	Signal	Example
Sort and Scan	"Maximum" or "Minimum" count	Activity Selection, Merge Intervals
Priority Queue	"Always pick best"	Task Scheduler, Huffman
Interval Scheduling	Non-overlapping intervals	Meeting Rooms, Non-overlapping Intervals
Jump Game	Reachability	Jump Game, Jump Game II

Interval problems are a classic greedy category.

Interval Sorting

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

Sort By	Strategy	Example
Start time	Process in order	Merge Intervals
End time	Pick non-overlapping	Activity Selection
Length	Pick shortest	Minimum Removal

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

Pattern	Complexity	Why
Sort and Scan	O(n log n)	Sorting dominates
Priority Queue	O(n log n)	Heap operations
Interval Scheduling	O(n log n)	Sorting
Two Pointers	O(n)	Single pass

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?