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. 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 can’t conflict with anything A didn’t conflict with. So we still have a valid solution with at least as many intervals.

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, take greedily.

double fractionalKnapsack(vector<pair<int, int>>& items, int W) {
    // Sort by value/weight ratio descending
    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.

long long minMergeCost(vector<int>& arr) {
    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();
        long long b = pq.top(); pq.pop();
        
        totalCost += a + b;
        pq.push(a + b);
    }
    
    return totalCost;
}

Pattern 5: Jump Game

Problem: Can you reach the last index? arr[i] = max jump from i. Greedy Strategy: Track the farthest position reachable.

bool canJump(vector<int>& nums) {
    int maxReach = 0;
    
    for (int i = 0; i < nums.size(); i++) {
        if (i > maxReach) return false;  // Can't reach position i
        maxReach = max(maxReach, i + nums[i]);
    }
    
    return true;
}

// Minimum jumps to reach end
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]);
        
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
        }
    }
    
    return jumps;
}

Pattern 6: Gas Station

Problem: Circular route with gas stations. Find starting point to complete circuit. Greedy Insight: If total gas ≥ total cost, solution exists. Start from the point where running sum is minimum.

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];
        total += diff;
        tank += diff;
        
        if (tank < 0) {
            start = i + 1;  // Can't start from any point before i+1
            tank = 0;
        }
    }
    
    return total >= 0 ? start : -1;
}

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

Getting Started

Fundamental Patterns

Greedy & Divide and Conquer

Dynamic Programming

Graph Algorithms

Advanced Topics

Contest Mastery

​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