Algorithm Templates: Greedy

Greedy algorithms are among the most elegant tools in competitive programming — when they work, they’re simpler and faster than dynamic programming. This guide covers the core greedy patterns you’ll encounter on LeetCode, with ready-to-use C++ templates for interval scheduling, activity selection, fractional knapsack, and greedy strategies on arrays and strings. Each section includes the key intuition so you know why the greedy choice is correct, not just how to code it.

New to Greedy? Greedy algorithms make the locally best choice at each step. Unlike DP, you never reconsider previous choices. The challenge is proving that local optimality leads to global optimality — if you can, greedy is simpler and faster than DP.

Greedy Algorithm Overview
Interval Scheduling
Activity Selection
Fractional Knapsack
Greedy on Arrays
Greedy on Strings
Greedy with Sorting

Greedy Algorithm Overview

Greedy algorithms make locally optimal choices at each step, hoping to find a global optimum. They work well when:

The problem has optimal substructure
The greedy choice property holds (locally optimal choice leads to global optimum)
No need to reconsider previous choices

Key Principles

Greedy Choice Property: A global optimum can be reached by making locally optimal choices. At every step, you pick what looks best right now and trust that this leads to the best overall answer.
Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems. After making a greedy choice, the remaining problem is a smaller instance of the same type.
No Backtracking: Once a choice is made, it’s never reconsidered. This is what makes greedy algorithms fast — but it also means you need to prove the greedy strategy is correct before relying on it.
Exchange Argument: The standard proof technique — assume an optimal solution differs from the greedy one, then show you can “exchange” a choice to match the greedy solution without making it worse.

Interval Scheduling

When to use: The problem mentions “non-overlapping intervals”, “minimum rooms”, “merge intervals”, or asks you to maximize/minimize a count of intervals that don’t conflict.

Greedy approach: Sort by end time, always pick the interval that ends earliest.

// Non-overlapping Intervals
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    if(intervals.empty()) return 0;
    
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];  // Sort by end time
    });
    
    int count = 1;
    int end = intervals[0][1];
    
    for(int i = 1; i < intervals.size(); i++) {
        if(intervals[i][0] >= end) {
            count++;
            end = intervals[i][1];
        }
    }
    
    return intervals.size() - count;
}

Activity Selection

When to use: The problem says “maximum activities”, “schedule as many as possible”, or “select non-conflicting events” — essentially interval scheduling phrased as a selection problem.

Similar to interval scheduling, select maximum number of non-overlapping activities.

// Maximum number of non-overlapping intervals
int maxNonOverlappingIntervals(vector<vector<int>>& intervals) {
    if(intervals.empty()) return 0;
    
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });
    
    int count = 1;
    int end = intervals[0][1];
    
    for(int i = 1; i < intervals.size(); i++) {
        if(intervals[i][0] >= end) {
            count++;
            end = intervals[i][1];
        }
    }
    
    return count;
}

Fractional Knapsack

When to use: You can take fractions of items (unlike 0/1 knapsack which needs DP). Look for “maximize value with limited capacity” where partial selections are allowed.

Greedy approach: Sort items by value/weight ratio, take items with highest ratio first.

// Fractional Knapsack (not a LeetCode problem, but classic greedy)
struct Item {
    int value, weight;
    double ratio;
};

double fractionalKnapsack(int W, vector<Item>& items) {
    sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.ratio > b.ratio;
    });
    
    double totalValue = 0.0;
    int remainingWeight = W;
    
    for(auto& item : items) {
        if(remainingWeight >= item.weight) {
            totalValue += item.value;
            remainingWeight -= item.weight;
        } else {
            totalValue += item.value * ((double)remainingWeight / item.weight);
            break;
        }
    }
    
    return totalValue;
}

Greedy on Arrays

When to use: Look for “jump game”, “maximum subarray”, “best time to buy/sell”, or any problem where you scan an array and maintain a running best/state — local decisions at each index build up to the global answer.

Greedy choices on array elements, often with two pointers or sliding window.

// Maximum Subarray (Kadane's Algorithm)
int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];
    
    for(int i = 1; i < nums.size(); i++) {
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSum = max(maxSum, currentSum);
    }
    
    return maxSum;
}

// Best Time to Buy and Sell Stock II
int maxProfit(vector<int>& prices) {
    int profit = 0;
    for(int i = 1; i < prices.size(); i++) {
        if(prices[i] > prices[i-1]) {
            profit += prices[i] - prices[i-1];
        }
    }
    return profit;
}

// Candy - Greedy with sequence tracking
int candy(vector<int>& ratings) {
    const int N = ratings.size();
    int rtn = 1;
    int inc = 1, dec = 0, pre = 1;
    for(int i = 1; i < N; i++) {
        if(ratings[i] >= ratings[i - 1]) {
            dec = 0;
            pre = ratings[i] == ratings[i - 1] ? 1: pre + 1;
            rtn += pre;
            inc = pre;
        } else {
            dec++;
            if(dec == inc) {
                dec++;
            }
            rtn += dec;
            pre = 1;
        }
    }
    return rtn;
}

// Wiggle Subsequence - Greedy with difference tracking
int wiggleMaxLength(vector<int>& nums) {
    const int N = nums.size();
    if(N < 2) return N;
    int prevDiff = nums[1] - nums[0];
    int rtn = prevDiff != 0? 2 : 1;
    for(int i = 2; i < N; i++) {
        int diff = nums[i] - nums[i - 1];
        if((diff > 0 && prevDiff <= 0) ||
            diff < 0 && prevDiff >= 0) {
                rtn++;
                prevDiff = diff;
            }
    }
    return rtn;
}

Greedy on Strings

When to use: The problem says “smallest subsequence”, “remove duplicate letters”, “minimum swaps”, or involves character frequency / ordering decisions — often solved with a stack-based greedy approach.

Greedy choices when processing strings, often with character frequency or ordering.

// Is Subsequence
bool isSubsequence(string s, string t) {
    int i = 0, j = 0;
    while(i < s.length() && j < t.length()) {
        if(s[i] == t[j]) {
            i++;
        }
        j++;
    }
    return i == s.length();
}

// Minimum Swaps to Make Strings Equal - Mismatch pairing
int minimumSwap(string s1, string s2) {
    int xy = 0, yx = 0;
    for(int i = 0; i < (int) s1.length(); i++) {
        if(s1[i] == 'x' && s2[i] == 'y') {
            xy++;
        } else if(s1[i] == 'y' && s2[i] == 'x') {
            yx++;
        }
    }
    if((xy + yx) % 2 == 1) {
        return -1;  // Impossible if odd total mismatches
    }
    return xy / 2 + yx / 2 + xy % 2 + yx % 2;
}

// Construct K Palindrome Strings - Frequency-based greedy
bool canConstruct(string s, int k) {
    int right = s.length();
    int occ[26] = {0};
    for(char ch: s) {
        occ[ch - 'a']++;
    }
    int left = 0;
    for(int i = 0; i < 26; i++) {
        if(occ[i] % 2 == 1) {
            left++;
        }
    }
    left = max(left, 1);
    return left <= k && k <= right;
}

Greedy with Sorting

When to use: The problem says “assign cookies”, “queue reconstruction”, “two city scheduling”, or any scenario where sorting by one dimension (size, cost difference, height) unlocks a simple greedy scan.

Many greedy problems require sorting first to make optimal choices.

// Assign Cookies
int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    
    int i = 0, j = 0;
    int count = 0;
    
    while(i < g.size() && j < s.size()) {
        if(s[j] >= g[i]) {
            count++;
            i++;
        }
        j++;
    }
    
    return count;
}

// Array Partition - Maximize sum of minimums
int arrayPairSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int sum = 0;
    for(int i = 0; i < (int)nums.size(); i += 2) {
        sum += nums[i];
    }
    return sum;
}

// Maximum Units on a Truck - Fractional knapsack style
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
    sort(boxTypes.begin(), boxTypes.end(), [](auto& u, auto& v){
        return u[1] > v[1];  // Sort by units per box (descending)
    });
    int remainSize = truckSize;
    int maximumUnits = 0;
    for(auto& boxType: boxTypes) {
        if(remainSize == 0) break;
        int cnt = min(remainSize, boxType[0]);
        maximumUnits += cnt * boxType[1];
        remainSize -= cnt;
    }
    return maximumUnits;
}

// Minimum Cost to Move Chips - Parity-based greedy
int minCostToMoveChips(vector<int>& position) {
    int even = 0, odd = 0;
    for(int pos : position) {
        if(pos % 2 == 0) {
            odd++;  // Count even positions
        } else {
            even++;  // Count odd positions
        }
    }
    return min(odd, even);  // Move minority parity to majority
}

// Two City Scheduling - Sort by cost difference
int twoCitySchedCost(vector<vector<int>>& costs) {
    sort(costs.begin(), costs.end(), [](auto& u, auto&v) {
        return (u[0] - u[1] < v[0] - v[1]);
    });
    int total = 0;
    const int N = costs.size() / 2;
    for(int i = 0; i < N; i++) {
        total += costs[i][0] + costs[i + N][1];
    }
    return total;
}

// Find Valid Matrix Given Row and Column Sums - Greedy two pointers
vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
    const int N = rowSum.size(), M = colSum.size();
    vector<vector<int>> matrix(N, vector<int>(M, 0));
    int i = 0, j = 0;
    while(i < N && j < M) {
        int v = min(rowSum[i], colSum[j]);
        matrix[i][j] = v;
        rowSum[i] -= v;
        colSum[j] -= v;
        if(rowSum[i] == 0) i++;
        if(colSum[j] == 0) j++;
    }
    return matrix;
}

// Queue Reconstruction by Height
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    sort(people.begin(), people.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
    });
    
    vector<vector<int>> result;
    for(auto& person : people) {
        result.insert(result.begin() + person[1], person);
    }
    
    return result;
}

Easy Problems

ID	Title	Link	Solution
455	Assign Cookies	Link	Solution
860	Lemonade Change	Link	Solution
392	Is Subsequence	Link	Solution
406	Queue Reconstruction by Height	Link	Solution
53	Maximum Subarray	Link	Solution
435	Non-overlapping Intervals	Link	Solution
452	Minimum Number of Arrows to Burst Balloons	Link	Solution
561	Array Partition	Link	Solution
1029	Two City Scheduling	Link	Solution
122	Best Time to Buy and Sell Stock II	Link	Solution
1710	Maximum Units on a Truck	Link	Solution
1217	Minimum Cost to Move Chips to The Same Position	Link	Solution

Medium Problems

ID	Title	Link	Solution
763	Partition Labels	Link	-
621	Task Scheduler	Link	-
435	Non-overlapping Intervals	Link	Solution
55	Jump Game	Link	Solution
1094	Car Pooling	Link	Solution
45	Jump Game II	Link	Solution
134	Gas Station	Link	-
1024	Video Stitching	Link	-
1247	Minimum Swaps to Make Strings Equal	Link	Solution
1400	Construct K Palindrome Strings	Link	Solution
1605	Find Valid Matrix Given Row and Column Sums	Link	Solution
376	Wiggle Subsequence	Link	Solution
274	H-Index	Link	Solution

Hard Problems

ID	Title	Link	Solution
135	Candy	Link	Solution
871	Minimum Number of Refueling Stops	Link	-
818	Race Car	Link	-
410	Split Array Largest Sum	Link	-
420	Strong Password Checker	Link	-
68	Text Justification	Link	-
76	Minimum Window Substring	Link	-
1799	Maximize Score After N Operations	Link	-

Common Greedy Patterns

1. Interval Problems

Sort by end time
Always pick the interval that ends earliest
Examples: Non-overlapping Intervals, Minimum Arrows to Burst Balloons

2. Two Pointers

Use two pointers to make greedy choices
Examples: Is Subsequence, Assign Cookies

3. Sorting + Greedy

Sort first, then apply greedy strategy
Examples: Queue Reconstruction by Height, Two City Scheduling

4. Local Optimization

Make best local choice at each step
Examples: Best Time to Buy and Sell Stock II, Maximum Subarray

5. Jump Problems

Greedy choice: jump as far as possible
Examples: Jump Game, Jump Game II

6. Scheduling Problems

Sort and schedule optimally
Examples: Task Scheduler, Car Pooling

Key Insights

When to use Greedy:
- Problem has optimal substructure
- Greedy choice property holds
- No need to reconsider previous choices
Common Mistakes:
- Not sorting when needed
- Wrong sorting criteria
- Not considering edge cases
- Assuming greedy always works (need to prove correctness)
Proving Greedy Correctness:
- Show greedy choice property
- Show optimal substructure
- Use exchange argument or contradiction

Dynamic Programming (when greedy doesn’t work)
Sorting Algorithms
Interval Problems
Two Pointers
Sliding Window

References

Mastering Greedy Algorithms with LeetCode - Comprehensive guide to greedy algorithms with LeetCode problems

Pattern Summary

Pattern	Signal Phrases	Key Idea
Interval Scheduling	“non-overlapping”, “minimum rooms”	Sort by end time, pick earliest
Activity Selection	“maximum activities”, “schedule”	Sort by end, greedily select
Greedy on Arrays	“jump game”, “max subarray”	Local decisions, running state
Greedy on Strings	“smallest subsequence”, “remove duplicates”	Stack-based greedy
Greedy + Sorting	“assign cookies”, “queue reconstruction”	Sort first, then greedily assign

More templates

Beginner’s Guide: LeetCode Beginner’s Guide
DP (when greedy doesn’t apply): Dynamic Programming
Data structures, Graph, Search: Data Structures & Core Algorithms, Graph, Search
Master index: Categories & Templates

Robina Li

Algorithm Templates: Greedy

Contents

Greedy Algorithm Overview

Key Principles

Interval Scheduling

Activity Selection

Fractional Knapsack

Greedy on Arrays

Greedy on Strings

Greedy with Sorting

Easy Problems

Medium Problems

Hard Problems

Common Greedy Patterns

1. Interval Problems

2. Two Pointers

3. Sorting + Greedy

4. Local Optimization

5. Jump Problems

6. Scheduling Problems

Key Insights

References

Pattern Summary

More templates

Related Posts

Recent Posts

Contents

Greedy Algorithm Overview

Key Principles

Interval Scheduling

Activity Selection

Fractional Knapsack

Greedy on Arrays

Greedy on Strings

Greedy with Sorting

Easy Problems

Medium Problems

Hard Problems

Common Greedy Patterns

1. Interval Problems

2. Two Pointers

3. Sorting + Greedy

4. Local Optimization

5. Jump Problems

6. Scheduling Problems

Key Insights

Related Topics

References

Pattern Summary

More templates

Related Posts

Recent Posts