Greedy Algorithms

Introduction

In the last two posts, we explored Dynamic Programming. DP is thorough, calculating every possible valid combination to guarantee the absolute best result. The downside? It uses a lot of memory and time.

What if we could skip all that exhaustive searching? What if we just looked at our current situation and made the most selfish, “best looking” immediate choice, hoping it leads to the best overall outcome?

Welcome to Greedy Algorithms.

What is a Greedy Algorithm?

A greedy algorithm makes the locally optimal choice at each stage with the hope of finding a global optimum.

Imagine you are driving and you hit a crossroads. You want to reach the highest mountain peak.

• A Dynamic Programming approach would send drones down every single path, map out the entire mountain range, sum the elevations, and print out the perfect route.
• A Greedy approach simply looks at the three roads in front of you, picks the one that goes up the steepest right now, and starts driving.

When do Greedy Algorithms work?

Greedy algorithms only work if the problem has the Greedy-Choice Property: making a locally optimal choice guarantees you don’t miss the globally optimal solution.

Example 1: The Classic Coin Change

Suppose you are a cashier giving change. You have coins sized [25c, 10c, 5c, 1c]. A customer needs 42c in change. You want to give them the minimum number of coins.

The Greedy Choice: Always pick the largest coin that is $\le$ the remaining amount.

1. Remaining: 42c. Largest coin $\le 42$ is 25c. (Take one 25c).
2. Remaining: 17c. Largest coin $\le 17$ is 10c. (Take one 10c).
3. Remaining: 7c. Largest coin $\le 7$ is 5c. (Take one 5c).
4. Remaining: 2c. Largest coin $\le 2$ is 1c. (Take two 1c).

Total coins: 1 Quarter, 1 Dime, 1 Nickel, 2 Pennies. (5 coins total). ✅ This is the proven mathematical minimum! The Greedy approach worked perfectly.

Example 2: When Greedy Fails

Let’s change the coinage. Suppose a strange country uses coins sized [25c, 20c, 1c]. A customer asks for 40c in change.

The Greedy Choice:

1. Remaining: 40c. Largest coin $\le 40$ is 25c.
2. Remaining: 15c. Largest coin $\le 15$ is 1c.
3. We have to give them 15 individual pennies!

Total coins: 1 Quarter + 15 Pennies = 16 coins. ❌

The Optimal Choice: Two 20c coins (2 coins).

Because the Greedy algorithm committed to the 25c coin immediately, it locked itself out of the true optimal path. This is the fatal flaw of Greedy Algorithms — they never backtrack. When Greedy fails, you must use Dynamic Programming.

Example 3: Activity Selection Problem

This is the most famous Greedy algorithmic problem.

You are given $N$ meetings, each with a start time and end time. You have one conference room. What is the maximum number of meetings you can schedule in that room?

The Wrong Greedy Choices

• Pick the shortest meeting first? No, it might sit right in the middle of the day, blocking two long meetings on either side.
• Pick the meeting that starts earliest? No, the earliest meeting might last 10 hours and block everything else.

The Correct Greedy Choice

Always pick the meeting that ENDS earliest.

If a meeting ends early, it frees up the room as fast as possible for subsequent meetings.

Java Implementation:

import java.util.Arrays;
import java.util.Comparator;

class Meeting {
    int start;
    int end;

    public Meeting(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class ActivitySelection {

    public static int maxMeetings(Meeting[] meetings) {
        if (meetings.length == 0) return 0;

        // Step 1: Sort meetings by their END time (Greedy strategy)
        Arrays.sort(meetings, Comparator.comparingInt(m -> m.end));

        int count = 1; // We always select the first meeting
        int lastEndTime = meetings[0].end;

        // Step 2: Iterate and greedily select non-overlapping meetings
        for (int i = 1; i < meetings.length; i++) {
            if (meetings[i].start >= lastEndTime) {
                // This meeting starts AFTER the last one ended. Take it!
                count++;
                lastEndTime = meetings[i].end;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        Meeting[] meetings = {
            new Meeting(1, 3), new Meeting(2, 5), 
            new Meeting(4, 6), new Meeting(6, 8), 
            new Meeting(5, 9), new Meeting(8, 10)
        };
        // Expecting 4: (1,3) -> (4,6) -> (6,8) -> (8,10)
        System.out.println("Max meetings: " + maxMeetings(meetings)); 
    }
}

Complexity

• Time: $O(n \log n)$ because we must sort the array first. The greedy selection pass is $O(n)$.
• Space: $O(1)$ (or $O(n)$ depending on the sorting algorithm under the hood).

Algorithms You Already Know That Are Greedy

You have actually been using Greedy algorithms without knowing it!

1. Dijkstra’s Shortest Path: Always picks the cheapest unvisited node from the Priority Queue.
2. Kruskal’s / Prim’s Algorithms: Always picks the shortest edge to build a Minimum Spanning Tree.
3. Selection Sort: Greedily searches the remaining array for the absolute minimum element.

Practice Problems

1. Jump Game – LeetCode #55 — A quintessential Greedy problem. Can you maintain a “max reach” variable?
2. Assign Cookies – LeetCode #455 — Direct application of sorting and greedy matching.
3. Gas Station – LeetCode #134 — A brilliant logic puzzle disguised as a coding problem.

What’s Next?

Greedy algorithms are incredibly fast, but as we saw with the 40-cent coin problem, they fail when they make a bad choice and cannot reverse it.

To solve problems where we must reverse our bad choices, we need a technique that methodically explores all options but is smart enough to abandon doomed paths early. That technique is called Backtracking.