Listen, I've seen a lot of developers—even some with a few years under their belt—fall into a specific mental trap when they first encounter greedy algorithms: they assume that if a problem looks like it's about optimization, the "best" immediate choice will naturally lead to the best global result. It feels intuitive. Why wouldn't you just take the biggest piece of the pie right now?

The Trap: "The Local Best is Always the Global Best"

Let's look at a concrete example where this intuition fails miserably. Imagine you're writing a program to make change for a specific amount of money using the fewest coins possible. You have denominations of 1, 3, and 4 cents. You need to make change for 6 cents.

A greedy approach would tell you: "Take the largest coin that fits first."

• Take a 4-cent coin. Remaining: 2 cents.
• Take a 1-cent coin. Remaining: 1 cent.
• Take a 1-cent coin. Remaining: 0 cents.
• Total: 3 coins.

But look closer. If you had just taken two 3-cent coins, you'd be done in 2 coins. The greedy choice (the 4-cent coin) actually blocked you from the optimal solution. This is why you can't just "wing it" with greedy patterns; you have to prove the Greedy Choice Property holds—meaning a local optimum actually leads to a global optimum.

The Correction: Leveraging Sorting and the Greedy Choice Property

For a greedy algorithm to actually work, the problem must have two things: optimal substructure (an optimal solution to the problem contains optimal solutions to its subproblems) and the greedy choice property. In C++, we almost always implement these patterns using a combination of std::sort or a std::priority_queue to keep our "best" options at the top of the pile.

A classic example where greedy actually does work is the Activity Selection Problem. If you have a list of meetings with start and end times, and you want to fit the maximum number of meetings into one room, the "local best" isn't the shortest meeting or the earliest starting meeting—it's the meeting that finishes first. By picking the activity that ends earliest, you leave as much room as possible for everyone else.

#include <iostream>
#include <vector>
#include <algorithm>

struct Activity {
    int start;
    int end;
    int id;
};

// The secret sauce: sort by end time, not start time.
bool compareActivities(const Activity& a, const Activity& b) {
    return a.end < b.end;
}

void selectMaxActivities(std::vector<Activity>& activities) {
    std::sort(activities.begin(), activities.end(), compareActivities);

    std::cout << "Selected Activities: ";
    
    // The first activity always gets picked because it ends earliest
    int last_end_time = activities[0].end;
    std::cout << activities[0].id << " ";

    for (size_t i = 1; i < activities.size(); ++i) {
        // If this activity starts after or when the last one ended, take it
        if (activities[i].start >= last_end_time) {
            std::cout << activities[i].id << " ";
            last_end_time = activities[i].end;
        }
    }
    std::cout << std::endl;
}

int main() {
    std::vector<Activity> acts = {{1, 4, 1}, {3, 5, 2}, {0, 6, 3}, {5, 7, 4}, {3, 8, 5}, {5, 9, 6}, {6, 10, 7}, {8, 11, 8}, {8, 12, 9}, {2, 14, 10}};
    selectMaxActivities(acts);
    return 0;
}

I want you to notice how the std::sort transforms the problem. Once the data is ordered by the finish time, the "greedy" choice of taking the first available activity is mathematically guaranteed to be part of an optimal solution. Without that sort, the greedy approach is just guessing.

When you're tackling these in the wild, ask yourself: "If I make this choice now, does it prevent me from making a better choice later?" If the answer is "yes," you probably need Dynamic Programming, not a Greedy algorithm. If the answer is "no," you've found your pattern.

📋 Practical Task

Implement a Minimum Number of Platforms Scheduler

You are managing a train station. You are given a list of arrival and departure times for all trains arriving in a day. Your goal is to find the minimum number of platforms required so that no train is forced to wait. This is a greedy problem: you need to track how many trains are at the station at any given moment.

Requirements:

• Create a function int findPlatform(int arr[], int dep[], int n).
• Sort both arrival and departure arrays independently.
• Use a two-pointer approach to track arrivals and departures. If a train arrives before the previous one departs, you need a new platform.
• The function should return the peak number of platforms needed simultaneously.

Test Case:
Arrivals: {900, 940, 950, 1100, 1500, 1800}
Departures: {910, 1200, 1120, 1130, 1900, 2000}
Expected Result: 3