Greedy Algorithms — Always Pick the Best

Real-world analogy

What is it?

A greedy algorithm is a problem-solving approach that makes the best possible choice at each step without reconsidering previous choices. It is like always picking the best option available right now. Greedy algorithms are fast and simple, but they only work for certain types of problems where local optimal choices lead to a global optimum.

Real-world relevance

Greedy algorithms power many real-world systems: GPS navigation (always take the shortest next road), Huffman coding in file compression (assign shortest codes to most frequent symbols), job scheduling in operating systems (shortest job first), and even how we naturally make decisions (take the closest parking spot).

Key points

• What is a Greedy Algorithm? — A greedy algorithm makes the locally optimal choice at each step, hoping this leads to a globally optimal solution. It never looks back or reconsiders previous choices. It is simple, fast, and — when it works — elegant.
• The Coin Change Problem (Greedy) — Given coins of 1, 5, 10, 25 cents, make change for 36 cents using the fewest coins. Greedy says: always pick the largest coin that fits. 25 + 10 + 1 = 36 cents, 3 coins. This works for standard US coin denominations!
• When Greedy Fails — Greedy does not always work! With coins [1, 3, 4], making change for 6: greedy picks 4+1+1 = 3 coins, but 3+3 = 2 coins is better! Greedy fails because picking the largest coin first is not always optimal with non-standard denominations.
• Activity Selection Problem — You have n activities with start and end times. You can only do one at a time. Greedy strategy: sort by end time, always pick the next activity that starts after the current one ends. This gives the maximum number of activities! And it is provably optimal.
• Why Sort by End Time? — Sorting by end time works because choosing the activity that finishes earliest leaves the most room for future activities. It is like always picking the shortest task first to fit more tasks into your day.
• Proving Greedy Works — To prove a greedy algorithm is correct, use the 'exchange argument': assume there is a better solution. Show you can swap choices to match the greedy solution without making things worse. If no swap makes it worse, greedy is optimal!
• Greedy vs Brute Force — Brute force tries all possible combinations — O(2^n) or worse. Greedy makes one choice per step — usually O(n log n) with sorting. When greedy works, it is DRAMATICALLY faster. The challenge is knowing when it works!
• Common Greedy Patterns — Look for greedy when: (1) the problem asks for minimum/maximum of something, (2) you can sort the data meaningfully, (3) making the locally best choice does not block better future choices, (4) the problem has an 'optimal substructure' — the best solution contains best sub-solutions.

Code example

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Problem 1: Coin Change (Greedy)
    int amount;
    cin >> amount;
    int coins[] = {25, 10, 5, 1};
    int totalCoins = 0;

    cout << "Making change for " << amount << " cents:\n";
    for (int i = 0; i < 4; i++) {
        int count = amount / coins[i];
        if (count > 0) {
            cout << count << " x " << coins[i] << " cents\n";
            totalCoins += count;
            amount %= coins[i];
        }
    }
    cout << "Total coins: " << totalCoins << "\n\n";

    // Problem 2: Activity Selection
    int n;
    cin >> n;
    vector<pair<int,int>> activities(n); // {end, start}
    for (int i = 0; i < n; i++) {
        int s, e;
        cin >> s >> e;
        activities[i] = {e, s}; // Store end first for sorting
    }
    sort(activities.begin(), activities.end()); // Sort by end time

    int count = 1;
    int lastEnd = activities[0].first;
    cout << "Selected: [" << activities[0].second << "," << activities[0].first << "]";

    for (int i = 1; i < n; i++) {
        if (activities[i].second >= lastEnd) { // Start >= last end
            count++;
            lastEnd = activities[i].first;
            cout << " [" << activities[i].second << "," << activities[i].first << "]";
        }
    }
    cout << "\nMax activities: " << count << "\n";

    return 0;
}

Line-by-line walkthrough

1. 1. int count = amount / coins[i]; — integer division tells us how many of this coin denomination we can use. For 36 / 25 = 1, we use one 25-cent coin.
2. 2. amount %= coins[i]; — the modulo gives us the remaining amount after using those coins. 36 % 25 = 11, so we still need 11 cents.
3. 3. activities[i] = {e, s}; — we store end time first in the pair. Since sort() orders pairs by first element, this automatically sorts by end time.
4. 4. sort(activities.begin(), activities.end()); — sorting by end time is the key greedy insight. The activity that ends earliest gives us the most room for future activities.
5. 5. if (activities[i].second >= lastEnd) — we check if this activity starts at or after the last selected activity ends. If so, there is no overlap and we can include it.
6. 6. lastEnd = activities[i].first; — update our tracking variable to the end time of the newly selected activity. Future activities must start after this time.

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int,int>> acts(n);
    for (int i = 0; i < n; i++) {
        cin >> acts[i].first >> acts[i].second; // start, end
    }
    sort(acts.begin(), acts.end()); // Sort by start time

    int count = 1;
    int lastEnd = acts[0].second;
    for (int i = 1; i < n; i++) {
        if (acts[i].first >= lastEnd) {
            count++;
            lastEnd = acts[i].second;
        }
    }
    cout << count << "\n";
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Greedy Algorithms (CP-Algorithms)
• Greedy Algorithms Explained (YouTube)
• Movie Festival (CSES)