Greedy algorithms have a reputation for being "simple," but that simplicity is exactly what makes them dangerous. The core idea is straightforward: at every step, you make the choice that looks best right now, hoping that these local wins will lead to a global victory. In Java, this usually translates to a sorting step followed by a single pass through a collection. But if you pick the wrong sorting criterion, your "optimal" solution will be wrong more often than it's right.

Why sorting by start time feels right but fails

Let's look at a classic scenario: Interval Scheduling. Imagine you have a single conference room and a list of meetings, each with a start and end time. You want to fit as many meetings as possible into that room. Your first instinct might be to be "fair" or "efficient" by picking the meeting that starts earliest. It feels logical—get things moving as soon as possible, right?

// The Naive Approach: Sorting by Start Time
public List<Interval> scheduleNaive(List<Interval> intervals) {
    intervals.sort(Comparator.comparingInt(i -> i.start));
    List<Interval> selected = new ArrayList<>();
    
    for (Interval current : intervals) {
        if (selected.isEmpty() || current.start >= selected.get(selected.size() - 1).end) {
            selected.add(current);
        }
    }
    return selected;
}

Here is where this breaks. Imagine a meeting that starts at 8:00 AM and lasts until 5:00 PM. If that's the earliest starting meeting, your algorithm grabs it and blocks the room for the entire day. Meanwhile, you might have had ten 30-minute meetings that could have fit in that same window. By being "greedy" about the start time, you've accidentally sabotaged your global goal of maximizing the number of meetings.

The "Earliest Finish" breakthrough

To actually solve this, we have to change what we are greedy about. Instead of looking at when a task starts, we look at when it ends. This is the critical insight for this pattern: by picking the task that finishes the earliest, you leave the maximum amount of remaining time available for everything else. It's a counter-intuitive shift in perspective, but it's mathematically guaranteed to give you the optimal number of activities.

// The Correct Greedy Approach: Sorting by End Time
public List<Interval> scheduleGreedy(List<Interval> intervals) {
    // The magic happens here: sort by end time, not start time
    intervals.sort(Comparator.comparingInt(i -> i.end));
    
    List<Interval> selected = new ArrayList<>();
    int lastEndTime = Integer.MIN_VALUE;

    for (Interval interval : intervals) {
        if (interval.start >= lastEndTime) {
            selected.add(interval);
            lastEndTime = interval.end;
        }
    }
    return selected;
}

Notice how the logic inside the loop remains almost identical to the naive version. The only thing that changed was the Comparator. This is typical of greedy patterns in Java: the heavy lifting is done by the sorting strategy. Once the data is ordered by the "greedy choice property," the actual selection process is usually just a linear scan (O(n)).

When greediness hits a wall

I should warn you: don't start applying this to every optimization problem you see. Greedy algorithms only work if the problem exhibits "optimal substructure"—meaning an optimal solution to the problem contains optimal solutions to its sub-problems.

Take the 0/1 Knapsack problem (where you can't break items into pieces). If you greedily take the most valuable item first, you might take up so much space that you can't fit three smaller items that combined are worth more. In those cases, greed fails, and you have to move toward Dynamic Programming. The trade-off is a massive increase in time and space complexity. If you can prove a greedy strategy works, you've just traded a complex recursive table for a simple Collections.sort() call. That's a win every time.

📋 Practical Task

Exercise: Optimizing a Satellite Downlink Schedule

You are writing software for a ground station that receives data bursts from a satellite. The satellite sends multiple data packets, but the antenna can only lock onto one packet at a time. Each packet has a specific startTime and endTime (in milliseconds). If packets overlap, you must choose one and discard the others.

Implement a class SatelliteScheduler with a method getMaxPackets(List<Packet> packets). Use the Greedy Algorithm pattern discussed in the lesson to return the maximum number of non-overlapping packets the station can successfully receive.

Requirements:

• Define a Packet record or class with int startTime and int endTime.
• The method should return an int representing the count of packets.
• Ensure your time complexity is dominated by the sort (O(n log n)).