Greedy Algorithms

Make the locally optimal choice at each step, sometimes that's globally optimal

You are paying with coins and you want to use as few as possible. What do you do? You grab the biggest coin that still fits, then the next biggest, and keep going. You do not stop to plan the whole thing. You just take the best you can see right now.
That is a greedy algorithm: at every step, grab the best-looking option in front of you, and never go back to rethink it.
The surprise is that this lazy little habit often gives the perfect answer. But not always. Play with the coins below, then switch to the tricky coins and watch greedy trip.

When greedy works, it is lovely: no planning, no undoing, just grab-the-best each step, and it is fast. It runs real things, like finding a short route on a map and squeezing files smaller.
When it fails, it fails the same way every time: it grabs a big prize now that blocks a better set later, like taking the 4 when two 3s would have been fewer coins.
So the real skill is spotting which kind of problem you have. If grabbing the best each step truly leads to the best overall, greedy is the simplest tool there is. If it might not, you reach for something that plans ahead and is willing to reconsider, like the dynamic programming from earlier. Greedy never looks back; DP does. That is the whole difference between them.

Interval scheduling, maximize non-overlapping intervalspython

def max_non_overlapping(intervals):
    """Select maximum number of non-overlapping intervals."""
    # Greedy: always pick the interval that ends earliest
    intervals.sort(key=lambda x: x[1])  # Sort by end time

    count = 1
    last_end = intervals[0][1]

    for start, end in intervals[1:]:
        if start >= last_end:  # No overlap
            count += 1
            last_end = end

    return count

intervals = [(1,3),(2,4),(3,5),(6,8)]
print(max_non_overlapping(intervals))  # → 3 ([1,3],[3,5],[6,8])

🤔Quick Check

Why does sorting by end time work for interval scheduling?

Practice Exercises

0/1 solved

Exercise 1 of 1medium

⏱ 00:00

Jump Game

Each element represents max jump length from that position. Can you reach the last index?
Expected output: True

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next