Greedy Algorithms

The Mental Model

Greedy is about making the best choice at each step without looking back. Imagine you’re collecting coins scattered on a path—you pick up the highest value coin at each position. Sometimes this works perfectly; sometimes it fails spectacularly.

Pattern Recognition Signals:

“Minimum number of operations/items”
“Maximum value/count possible”
Problem has optimal substructure + greedy choice property
Sorting + processing often leads to answer

When Greedy Works (and When It Doesn’t)

Greedy Works When

Local optimal leads to global optimal
No need to reconsider past choices
Exchange argument can prove correctness
Problem has “greedy choice property”

Greedy Fails When

Current choice affects future options
Need to try all possibilities (use DP)
Counter-example exists
Problem mentions “subsequence” (often DP)

The Greedy Proof: Exchange Argument

To prove greedy works, show that swapping from greedy to non-greedy never improves the answer. This is the most common proof technique for greedy algorithms in competitive programming. The template:

Assume an optimal solution O that differs from the greedy solution G
Find the first place where they differ
Show you can “exchange” O’s choice for G’s choice without making things worse
Repeat until O matches G — proving G is also optimal

Example: Activity Selection (select max non-overlapping intervals) Greedy: Always pick the interval that ends earliest. Proof: Suppose optimal solution picks interval A instead of greedy’s choice B (where B ends earlier). Replace A with B. Since B ends earlier, it cannot conflict with anything A did not conflict with. So we still have a valid solution with at least as many intervals. By repeating this exchange, we can transform the optimal solution into the greedy solution without losing any intervals.

Contest tip: You do not need to write a formal proof during a contest. But you should mentally verify the exchange argument in 30 seconds. If you cannot convince yourself that swapping is safe, the greedy is probably wrong—consider DP instead.

Pattern 1: Interval Scheduling

Problem: Select maximum number of non-overlapping intervals. Greedy Strategy: Sort by end time, always pick next non-overlapping.

int maxNonOverlapping(vector<pair<int, int>>& intervals) {
    // Sort by end time
    sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
        return a.second < b.second;
    });
    
    int count = 0, lastEnd = INT_MIN;
    
    for (auto& [start, end] : intervals) {
        if (start >= lastEnd) {
            count++;
            lastEnd = end;
        }
    }
    
    return count;
}

Why End Time?: An interval that ends early leaves more room for future intervals. Codeforces Problems:

Problem	Rating	Link
Classroom Watch	1200	CF 875A
Movie Festival	-	CSES

Pattern 2: Task Scheduling with Deadlines

Problem: Tasks have deadlines and durations. Minimize lateness. Greedy Strategy: Sort by deadline (Earliest Deadline First).

int minLateness(vector<pair<int, int>>& tasks) {  // {duration, deadline}
    sort(tasks.begin(), tasks.end(), [](auto& a, auto& b) {
        return a.second < b.second;  // Sort by deadline
    });
    
    int time = 0, maxLate = 0;
    
    for (auto& [duration, deadline] : tasks) {
        time += duration;
        maxLate = max(maxLate, time - deadline);
    }
    
    return maxLate;
}

Pattern 3: Fractional Knapsack

Problem: Items have weight and value. Maximize value in capacity W. Can take fractions. Greedy Strategy: Sort by value/weight ratio (value per unit weight), take as much as possible of the best items first. Why this works: Since we can take fractions, there is no penalty for “partially using” an item. The optimal strategy is to always take the item giving you the most value per kilogram.

double fractionalKnapsack(vector<pair<int, int>>& items, int W) {
    // Sort by value/weight ratio descending -- most valuable per unit first
    sort(items.begin(), items.end(), [](auto& a, auto& b) {
        return (double)a.second / a.first > (double)b.second / b.first;
    });
    
    double totalValue = 0;
    
    for (auto& [weight, value] : items) {
        if (W >= weight) {
            W -= weight;
            totalValue += value;
        } else {
            totalValue += (double)W / weight * value;
            break;
        }
    }
    
    return totalValue;
}

0/1 Knapsack: If you can’t take fractions, greedy fails. Use DP instead.

Pattern 4: Huffman Encoding (Min Cost Merging)

Problem: Merge elements repeatedly, cost = sum of merged elements. Minimize total cost. Greedy Strategy: Always merge the two smallest. Why the two smallest? Every element’s value gets “re-paid” at every merge it participates in. Elements merged later participate in fewer future merges. So putting the largest elements into late merges (few future payments) and smallest into early merges (many future payments) minimizes total cost. Worked Example: arr = [1, 2, 3, 4]

Merge 1 + 2 = 3, cost = 3. Array: [3, 3, 4]
Merge 3 + 3 = 6, cost = 6. Array: [4, 6]
Merge 4 + 6 = 10, cost = 10. Array: [10]
Total cost = 3 + 6 + 10 = 19

If instead we merged largest first: 3+4=7 (cost 7), 2+7=9 (cost 9), 1+9=10 (cost 10). Total = 26. Worse.

long long minMergeCost(vector<int>& arr) {
    // Min-heap: always access the two smallest elements
    priority_queue<long long, vector<long long>, greater<long long>> pq(arr.begin(), arr.end());
    
    long long totalCost = 0;
    
    while (pq.size() > 1) {
        long long a = pq.top(); pq.pop();  // Smallest
        long long b = pq.top(); pq.pop();  // Second smallest
        
        totalCost += a + b;    // Pay the merge cost
        pq.push(a + b);        // Merged element goes back into the heap
    }
    
    return totalCost;
}
// Time: O(n log n) -- n-1 merges, each with O(log n) heap operations

Pattern 5: Jump Game

Problem: Can you reach the last index? arr[i] = max jump from i. Greedy Strategy: Track the farthest position reachable. Analogy: Imagine you are walking along a number line. At each position, you see how far ahead you could leap. You do not actually need to jump at every position — you just keep track of the farthest point any position so far could reach. If at any position i you find you could never have gotten there (i > maxReach), the answer is “no.”

bool canJump(vector<int>& nums) {
    int maxReach = 0;  // The farthest index we can reach so far
    
    for (int i = 0; i < nums.size(); i++) {
        if (i > maxReach) return false;  // Can't reach position i at all
        maxReach = max(maxReach, i + nums[i]);  // Extend our reach
    }
    
    return true;  // maxReach >= n-1
}

// Minimum jumps to reach end (BFS-like greedy)
// Think of it as BFS levels: each "jump" covers a range of positions
int minJumps(vector<int>& nums) {
    int jumps = 0, currentEnd = 0, farthest = 0;
    
    for (int i = 0; i < nums.size() - 1; i++) {
        farthest = max(farthest, i + nums[i]);  // Farthest reach from current level
        
        if (i == currentEnd) {  // Exhausted current jump's range
            jumps++;             // Must take another jump
            currentEnd = farthest;  // New range boundary
            // If currentEnd >= n-1, we will reach the end
        }
    }
    
    return jumps;
}
// Worked example: nums = [2, 3, 1, 1, 4]
// i=0: farthest=2, i==currentEnd(0) -> jumps=1, currentEnd=2
// i=1: farthest=4, i!=2
// i=2: farthest=4, i==currentEnd(2) -> jumps=2, currentEnd=4
// Answer: 2 jumps (0->1->4)

Pattern 6: Gas Station

Problem: Circular route with gas stations. Find starting point to complete circuit. Greedy Insight: If total gas >= total cost, a solution exists. Start from the point where running sum is minimum. Why this works: If the tank drops below 0 at station i, no station from the current start through i can be the answer (they would all run out of gas at or before i). So we reset and try starting from i + 1. If the total gas is sufficient globally, the last reset point is guaranteed to work. Edge case: If all gas[i] == cost[i], the answer is 0 (any starting point works since the tank never goes negative). If total gas < total cost, no starting point works.

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int total = 0, tank = 0, start = 0;
    
    for (int i = 0; i < gas.size(); i++) {
        int diff = gas[i] - cost[i];  // Net gas gain at station i
        total += diff;  // Track global gas balance
        tank += diff;   // Track current attempt's gas balance
        
        if (tank < 0) {
            start = i + 1;  // Can't start from any station [start..i]
            tank = 0;       // Reset tank for new starting attempt
        }
    }
    
    return total >= 0 ? start : -1;  // -1 if total gas < total cost
}

Common Greedy Mistakes

Mistake 1: Assuming Greedy Without Proof Always verify with edge cases or construct a counter-example:

Greedy for 0/1 Knapsack?
Items: [(5, 10), (4, 40), (6, 30)]  // (weight, value)
Capacity: 10

Greedy by ratio: take (4, 40) then can't fit rest
Value = 40

Optimal: take (4, 40) and (6, 30) doesn't fit... 
Wait, take (5, 10) and... no

Actually take (4, 40): W=6 left, take nothing else = 40
Or take (5, 10) and nothing else = 10
Or take (6, 30) and (4, 40) = doesn't fit

Actually optimal is 40 + 30 if we could fit (6)... can't.
Greedy works here, but in general 0/1 knapsack needs DP.

Mistake 2: Wrong Sorting Criteria Small changes in sort order can break greedy:

// WRONG for interval scheduling
sort(intervals.begin(), intervals.end());  // Sorts by start time

// CORRECT
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
    return a.second < b.second;  // Sort by END time
});

Mistake 3: Greedy When DP Needed Signals that greedy fails:

“Longest increasing subsequence” (not subarray)
“Number of ways”
Choices affect future options
Classic problem known to need DP

The Greedy Decision Flowchart

Can you sort the input?
├── Yes → After sorting, can you process greedily?
│   ├── Yes → Try to prove with exchange argument
│   │   ├── Proof works → Use greedy
│   │   └── Can't prove → Test edge cases, maybe DP
│   └── No clear greedy order → Likely DP or other
└── No → Is there a single pass greedy?
    ├── Yes → Track running max/min/sum
    └── No → Probably not greedy

Practice Problems

Beginner (800-1100)

Problem	Pattern	Link
Watermelon	Simple greedy	CF 4A
Team	Counting greedy	CF 231A
Petya and Strings	Comparison	CF 112A

Intermediate (1100-1400)

Problem	Pattern	Link
Minimum Penalty	Sorting + greedy	CF 1409C
Maximum Swap	Local greedy	LeetCode 670
Tasks	Interval scheduling	CF 978F

Advanced (1400-1700)

Problem	Pattern	Link
Wi-Fi	Interval coverage	CF 1216C
Hard Problem	Sorting + greedy	CF 706C
Array Splitting	Greedy selection	CF 1175B

Key Takeaways

Exchange Argument

Prove greedy by showing swaps don’t help.

Sort First

Most greedy solutions start with sorting.

Trust But Verify

Greedy intuition can be wrong. Test edge cases.

Know When to DP

“Subsequence” and “count ways” usually need DP.

Next Up

Chapter 10: Divide & Conquer

Learn to split problems in half, solve each part, and combine results efficiently.

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

Greedy Algorithms

Greedy Algorithms

The Mental Model

When Greedy Works (and When It Doesn’t)

Greedy Works When

Greedy Fails When

The Greedy Proof: Exchange Argument

Pattern 1: Interval Scheduling

Pattern 2: Task Scheduling with Deadlines

Pattern 3: Fractional Knapsack

Pattern 4: Huffman Encoding (Min Cost Merging)

Pattern 5: Jump Game

Pattern 6: Gas Station

Common Greedy Mistakes

The Greedy Decision Flowchart

Practice Problems

Beginner (800-1100)

Intermediate (1100-1400)

Advanced (1400-1700)

Key Takeaways

Exchange Argument

Sort First

Trust But Verify

Know When to DP

Next Up

Chapter 10: Divide & Conquer

​Greedy Algorithms

​The Mental Model

​When Greedy Works (and When It Doesn’t)

Greedy Works When

Greedy Fails When

​The Greedy Proof: Exchange Argument

​Pattern 1: Interval Scheduling

​Pattern 2: Task Scheduling with Deadlines

​Pattern 3: Fractional Knapsack

​Pattern 4: Huffman Encoding (Min Cost Merging)

​Pattern 5: Jump Game

​Pattern 6: Gas Station

​Common Greedy Mistakes

​The Greedy Decision Flowchart

​Practice Problems

​Beginner (800-1100)

​Intermediate (1100-1400)

​Advanced (1400-1700)

​Key Takeaways

Exchange Argument

Sort First

Trust But Verify

Know When to DP

​Next Up

Chapter 10: Divide & Conquer

Greedy Algorithms

The Mental Model

When Greedy Works (and When It Doesn’t)

The Greedy Proof: Exchange Argument

Pattern 1: Interval Scheduling

Pattern 2: Task Scheduling with Deadlines

Pattern 3: Fractional Knapsack

Pattern 4: Huffman Encoding (Min Cost Merging)

Pattern 5: Jump Game

Pattern 6: Gas Station

Common Greedy Mistakes

The Greedy Decision Flowchart

Practice Problems

Beginner (800-1100)

Intermediate (1100-1400)

Advanced (1400-1700)

Key Takeaways

Next Up