Greedy Algorithms That Actually Work: How to Recognize and Solve Them

Why greedy shows up so often in interviews

Greedy problems are common in interviews because they test a useful skill: can you make a locally optimal choice without painting yourself into a corner? That sounds simple, but it is easy to get wrong. Many problems look greedy at first and turn out to need dynamic programming. Others are genuinely greedy, but only if you choose the right invariant.

The difference matters. If you can identify a valid greedy strategy quickly, you often get an elegant O(n) or O(n log n) solution. If you guess wrong, you may end up with a solution that fails on a small counterexample.

In this post, you will learn how to recognize greedy problems, why some greedy choices are safe, and how to solve three interview staples:

• interval scheduling
• jump game
• gas station

Problem statement: what makes a greedy problem?

A greedy algorithm makes the best immediate choice at each step, then moves forward without revisiting earlier decisions.

That only works when two things are true:

1. Greedy choice property: a locally optimal choice can be part of a globally optimal solution.
2. Optimal substructure: after making that choice, the remaining problem is still optimal in the same sense.

The interview challenge is not coding the greedy loop. It is proving to yourself that the choice is safe.

A quick mental test

When you see a problem, ask:

• Can I sort the candidates by some useful key?
• Can I define a progress metric that only moves forward?
• If I choose the “best” local option now, can I prove I never need to undo it?
• Can I build an exchange argument, where any optimal solution can be transformed to include my choice?

If the answer is yes, greedy may work.

Intuition: why greedy works when it works

The best greedy solutions usually have one of these shapes:

• Earliest finishing time: choose the interval that leaves the most room for the future.
• Farthest reach: among all current options, choose the one that extends your progress the most.
• Minimum required resource: choose the action that prevents failure as long as possible.

These are not random rules. They preserve flexibility.

A good greedy choice does one of two things:

• leaves the remaining problem as large as possible for future choices
• guarantees you do not lose any optimal solution by taking it

That is why a greedy algorithm often feels almost too simple once you see it. The hard part is finding the right choice metric.

Approach 1: Interval scheduling

Problem

Given a list of intervals, select the maximum number of non-overlapping intervals.

Example:

[(1, 3), (2, 4), (3, 5), (0, 6), (5, 7), (8, 9)]

A valid answer is 4 intervals, for example:

(1, 3), (3, 5), (5, 7), (8, 9)

Why the greedy choice is to pick the earliest finishing interval

If you want to fit in as many intervals as possible, the interval that ends first leaves the most room for what comes next.

This is a classic exchange argument:

• Suppose an optimal solution starts with some interval A.
• If there is another interval B that ends earlier than A and is compatible with everything A is compatible with, then swapping A for B cannot hurt.
• Therefore, there exists an optimal solution that picks the earliest finishing interval first.

Repeat that logic after each selection.

Python solution

from typing import List, Tuple

def max_non_overlapping(intervals: List[Tuple[int, int]]) -> int:
    intervals.sort(key=lambda x: x[1])  # sort by end time
    count = 0
    last_end = float('-inf')

    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end

    return count

Worked example

Input:

intervals = [(1, 3), (2, 4), (3, 5), (0, 6), (5, 7), (8, 9)]

Sorted by end time:

(1, 3), (2, 4), (3, 5), (0, 6), (5, 7), (8, 9)

Trace:

• start with last_end = -inf
• pick (1, 3) → count = 1, last_end = 3
• skip (2, 4) because 2 < 3
• pick (3, 5) → count = 2, last_end = 5
• skip (0, 6) because 0 < 5
• pick (5, 7) → count = 3, last_end = 7
• pick (8, 9) → count = 4, last_end = 9

Why this works

If you choose a later-finishing interval when an earlier-finishing one was available, you only reduce future options. So the greedy choice is safe.

Approach 2: Jump Game

Problem

You are given an array nums, where nums[i] is the maximum jump length from position i. Determine whether you can reach the last index.

Example:

nums = [2, 3, 1, 1, 4]

You can reach the end.

The greedy insight

Instead of simulating every jump path, track the farthest index you can reach so far.

If your current index goes beyond that farthest reach, you are stuck.

This works because the only thing that matters is the best reach you have accumulated. You do not need to remember which path got you there.

Python solution

from typing import List

def can_jump(nums: List[int]) -> bool:
    farthest = 0

    for i, jump in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + jump)
        if farthest >= len(nums) - 1:
            return True

    return True

Worked example

Input:

nums = [2, 3, 1, 1, 4]

Trace:

• farthest = 0
• i = 0, jump = 2 → farthest = max(0, 0 + 2) = 2
• i = 1, reachable because 1 <= 2 → farthest = max(2, 1 + 3) = 4
• farthest >= last index, so return True

Now consider:

nums = [3, 2, 1, 0, 4]

Trace:

• i = 0, farthest = 3
• i = 1, farthest = 3
• i = 2, farthest = 3
• i = 3, farthest = 3
• i = 4, but 4 > farthest, so return False

Why this works

Once you know the furthest position reachable from any visited index, that is enough information. If you cannot reach a new index, no future jump can help, because all future jumps depend on reaching them first.

Approach 3: Gas Station

Problem

You have a circular route of gas stations. At station i, you gain gas[i] fuel and spend cost[i] fuel to go to the next station. Find the starting station index that lets you complete the circuit, or return -1 if impossible.

Greedy insight

There are two key observations:

1. If total gas is less than total cost, no solution exists.
2. If you fail to reach station j from starting station start, then none of the stations between start and j can be a valid start either.

That second fact is the greedy core. When your running tank goes negative, you restart from the next station instead of trying every earlier station.

Python solution

from typing import List

def can_complete_circuit(gas: List[int], cost: List[int]) -> int:
    if sum(gas) < sum(cost):
        return -1

    start = 0
    tank = 0

    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0

    return start

Worked example

Input:

gas =  [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]

First check totals:

• total gas = 15
• total cost = 15

A solution may exist.

Trace:

• start = 0, tank = 0
• station 0: tank += 1 - 3 = -2 → fail, so set start = 1, tank = 0
• station 1: tank += 2 - 4 = -2 → fail, so set start = 2, tank = 0
• station 2: tank += 3 - 5 = -2 → fail, so set start = 3, tank = 0
• station 3: tank += 4 - 1 = 3
• station 4: tank += 5 - 2 = 6

Return 3.

Why this works

If starting at station start fails at station i, then every station between start and i accumulates even less fuel before reaching i. So none of them can succeed either. That lets you discard a whole range at once.

A useful comparison: greedy vs. brute force vs. dynamic programming

Some problems tempt you into trying every choice. Greedy can replace that search when you can prove a safe local rule.

How to recognize greedy problems in interviews

Look for these signals:

• You need to maximize count, reach, or remaining flexibility.
• Choices can be ordered by one key: earliest end, farthest reach, smallest cost, highest reward.
• The problem has a circular or linear scan with a rolling invariant.
• A failed attempt can eliminate a range of candidates, not just one.

Red flags that greedy may not work

• The best local choice depends on future information in a complicated way.
• You need to reconsider earlier decisions often.
• There are overlapping subproblems where different paths to the same state matter.

When you see those signs, dynamic programming may be a better fit.

Common interview mistakes

• Choosing the wrong sort key in interval problems. Ending time matters more than start time for maximum count.
• Tracking too much state in Jump Game. You only need the farthest reachable index, not the exact path.
• Skipping the feasibility check in Gas Station. If total gas is less than total cost, no start can work.
• Assuming greedy is obvious. You still need an argument for why the choice is safe.

Key takeaways

• Greedy works when a local choice can be proven safe for the global optimum.
• The proof usually comes from an exchange argument or a range-elimination argument.
• Interval scheduling uses earliest finishing time.
• Jump Game uses farthest reachable position.
• Gas Station uses a reset rule after a failed prefix.
• In interviews, focus less on “what feels right” and more on “what invariant stays true.”

Related problems to practice

These problems reinforce the same pattern:

• Meeting Rooms II
• Non-overlapping Intervals
• Minimum Number of Arrows to Burst Balloons
• Jump Game II
• Partition Labels
• Task Scheduler

If you want to trace the variable updates step by step, I built an interactive version of this walkthrough at codebrew.ai — it can help if you learn best by watching the state change.

Practice these next

1. Non-overlapping Intervals — remove the minimum number of intervals to make the rest non-overlapping.
2. Jump Game II — compute the minimum number of jumps to reach the last index.
3. Minimum Number of Arrows to Burst Balloons — another interval greedy problem.
4. Partition Labels — cut a string into as many parts as possible so letters do not cross partitions.
5. Task Scheduler — reason about cooldowns and frequency-based greedy choices.