Greedy vs DP: 5 Problems Where Greedy Wins

I've been breaking down coding patterns that gave me trouble, and this one hit me in a specific way. After spending weeks drilling the dynamic programming algorithm approach, I started seeing DP everywhere. Every optimization problem? DP. Every "find the minimum/maximum"? DP. I was building tables and memoizing recursive calls for problems that had elegant two-pointer or sorting-based greedy algorithm solutions sitting right there.

This post walks through 5 greedy vs DP problems where I went straight to dynamic programming, wasted time on an overcomplicated solution, and then realized greedy was not only simpler but often faster. If you've been defaulting to DP for every optimization problem in your coding interview prep, this might change how you think about algorithm selection.

Why Dynamic Programming vs Greedy Confused Me

After you learn the dynamic programming algorithm, it feels like a superpower. You can break any problem into subproblems, store results, and avoid redundant work. The issue is that DP is a hammer, and once you have it, everything looks like a nail.

The greedy algorithm vs dynamic programming distinction requires a different kind of confidence. With DP, you explore all possibilities and pick the best. With the greedy approach, you commit to one choice at each step and never look back. That feels risky when you're preparing for coding interviews. What if the locally optimal choice isn't globally optimal? What if you need to backtrack?

The thing I didn't understand early on: for certain problems, you can prove that the greedy choice property guarantees the local optimum leads to the global optimum. And when that's the case, greedy gives you the same answer as DP with a fraction of the time and space complexity. This applies across problem types, from graph algorithms like shortest path problems to interval scheduling and even minimum spanning tree construction.

Here's how I learned that lesson across 5 problems.

Problem 1: Activity Selection (The Classic Wake-Up Call)

The problem: You have a list of activities with start and end times. The goal is to maximize the number of non-overlapping activities you can attend. This is a classic computer science problem that appears in algorithm courses and coding interviews.

My DP approach

I sorted the activities by start time, then tried to build a DP table. For each activity, I considered two options: include it (and skip all overlapping ones) or exclude it. I used binary search to find the next non-overlapping activity after including the current one. The time complexity was O(n log n) for sorting plus O(n) for DP with binary search lookups. It worked, but the code was long and I kept getting off-by-one errors with the binary search.

The greedy insight

Sort by end time instead. Always pick the activity that ends earliest. Then skip everything that overlaps with it and pick the next earliest-ending one.

def max_activities(activities):
    activities.sort(key=lambda x: x[1])  # sort by end time
    count = 1
    last_end = activities[0][1]

    for start, end in activities[1:]:
        if start >= last_end:
            count += 1
            last_end = end

    return count

Why greedy works here

By picking the activity that ends earliest, you leave the most room for future activities. If you ever picked a later-ending activity instead, you'd block at least as many future options. You can swap any non-greedy choice for the greedy one without losing anything. This is called an exchange argument, and it's the core proof technique for greedy algorithms.

That was nine lines of code versus my 30+ line DP solution. Same correct answer. Way simpler.

Problem 2: Jump Game (LeetCode 55)

The problem: Given an array where each element represents the maximum jump length from that position, determine if you can reach the last index starting from the first.

The DP trap

I built a bottom-up DP array where dp[i] meant "can I reach position i?" For each position, I looked at all earlier positions to see if any could jump to the current one. O(n^2) time. It passed, but barely, and the logic felt clunky.

# The overcomplicated DP version
def can_jump_dp(nums):
    n = len(nums)
    dp = [False] * n
    dp[0] = True
    for i in range(1, n):
        for j in range(i):
            if dp[j] and j + nums[j] >= i:
                dp[i] = True
                break
    return dp[n - 1]

The greedy fix

Track the farthest index you can reach. Walk through the array. At each position, update the max reachable index. If your current position ever exceeds the max reachable, you're stuck.

def can_jump(nums):
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + jump)
    return True

The signal I missed

The problem doesn't ask HOW to get there or the minimum number of jumps. It asks WHETHER you can get there. That's a binary question. You don't need to track paths or possibilities. You just need to know the farthest point reachable, and greedy tracking gives you that with O(n) time complexity and O(1) space. Understanding the time complexity difference between greedy and DP approaches is key to picking the right algorithm in interviews.

Problem 3: Fractional Knapsack

The problem: You have items with weights and values, and a knapsack with a weight capacity. Maximize the total value you can carry. Unlike 0/1 knapsack, you can take fractions of items.

Why my brain went to 0/1 knapsack DP

I'd just finished solving the classic 0/1 knapsack problem with a 2D DP table. When I saw "knapsack" in the problem name, I immediately started building a DP solution. Then I realized the fractions part changes everything.

The "fractions change everything" moment

In 0/1 knapsack, you either take an item or leave it. That creates genuinely overlapping subproblems because each decision affects what's available later. But with fractions, there's no binary choice. You can take exactly as much of each item as you want. That means you should always take the most valuable stuff first.

def fractional_knapsack(capacity, items):
    # items is list of (weight, value)
    # sort by value-to-weight ratio, highest first
    items.sort(key=lambda x: x[1] / x[0], reverse=True)

    total_value = 0
    remaining = capacity

    for weight, value in items:
        if remaining >= weight:
            total_value += value
            remaining -= weight
        else:
            total_value += value * (remaining / weight)
            break

    return total_value

The greedy proof is intuitive

If you have remaining capacity, you should always fill it with the item that gives you the most value per unit weight. Taking a lower-ratio item first would mean getting less value for the same weight. There's no scenario where saving capacity for a worse ratio pays off, because you can always take fractions.

Problem 4: Minimum Number of Platforms (Meeting Rooms II)

The problem: Given arrival and departure times of trains at a station, find the minimum number of platforms needed so no train waits.

My DP instinct

I started thinking about this as a state problem. At each moment in time, some number of platforms are in use. I tried to model transitions between states. It got complicated fast because the state space was huge (time could be any value), and I was essentially trying to simulate the timeline.

The greedy approach

Separate arrivals and departures into two sorted arrays. Use two pointers to sweep through time. When an arrival comes before the next departure, you need an additional platform. When a departure comes first, you free one up.

def min_platforms(arrivals, departures):
    arrivals.sort()
    departures.sort()

    platforms = 0
    max_platforms = 0
    i, j = 0, 0

    while i < len(arrivals):
        if arrivals[i] <= departures[j]:
            platforms += 1
            max_platforms = max(max_platforms, platforms)
            i += 1
        else:
            platforms -= 1
            j += 1

    return max_platforms

Why this works

You don't care which train is on which platform. You only care about how many platforms are occupied at any point. Sorting and sweeping gives you that count directly. The greedy part is that you process events in chronological order and make the obvious decision at each event: a train arrives, add a platform. A train departs, free one. The maximum at any point is your answer.

O(n log n) for sorting, O(n) for the sweep. No DP table needed.

Problem 5: Gas Station (LeetCode 134)

The problem: There are n gas stations arranged in a circle. At station i, you get gas[i] fuel and it costs cost[i] to travel to the next station. Find the starting station index that lets you complete the full circuit. If no solution exists, return -1.

My brute force attempt

I tried every starting point and simulated the trip. O(n^2). Then I thought about DP: maybe I could memoize partial circuits? But the circular structure made it awkward to define subproblems cleanly.

The greedy observation

Two key insights make this greedy. First, if the total gas across all stations is at least the total cost, a valid starting point must exist. Second, if you start at station s and run out of gas at station f, then no station between s and f can be a valid start either (because you arrived at each of those with some positive surplus, and they still couldn't make it past f).

def can_complete_circuit(gas, cost):
    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

Why greedy works

The first check (total gas >= total cost) guarantees a solution exists. Then you sweep through once. Whenever your running tank goes negative, everything from your current start to this point is a dead end. Reset and try starting from the next station. The proof relies on the fact that if a segment has a net negative, no sub-segment starting within it can overcome that deficit.

O(n) time, O(1) space. My brute force was 100x slower on large inputs.

How to Spot Greedy vs DP Problems in Interviews

After going through these problems, I started noticing signals that distinguish greedy algorithm vs dynamic programming problems in interview settings.

The greedy choice property holds. At each step, you can make a choice that's clearly best without needing to evaluate future consequences. In activity selection, the earliest-ending activity is always safe to pick. In jump game, the farthest reachable point always captures the answer. Classic greedy algorithms like Dijkstra's shortest path and Kruskal's minimum spanning tree algorithm both rely on this property.

You never need to backtrack or reconsider. If your solution requires looking at past decisions and potentially changing them, that's DP territory. The greedy approach moves forward and never looks back.

The problem asks for one aggregate answer. "Can you reach the end?" "What's the maximum number?" "What's the minimum count?" These are often greedy-friendly. If the problem asks for all possible solutions or the actual sequence of decisions, the dynamic programming algorithm is more appropriate.

The exchange argument works. Can you always replace a non-greedy choice with the greedy one without making the answer worse? If yes, greedy is provably correct. This is the same reasoning behind why minimum spanning trees use greedy edge selection.

Sorting unlocks the solution. Many greedy problems become obvious once you sort the input by the right key: end times, ratios, deadlines, or values. If sorting the input makes a simple left-to-right scan work, that's a greedy algorithm pattern.

When Greedy Fails and You Need Dynamic Programming

Not every optimization problem has a greedy solution. Here are problems where the greedy approach looks tempting but breaks, and the dynamic programming algorithm is necessary.

0/1 Knapsack is the classic counterexample. You can't take fractions, so the best value-to-weight ratio doesn't guarantee the best total value. You need the DP table to explore all take-or-leave combinations. This is fundamentally different from the fractional knapsack because the greedy choice property doesn't hold.

Longest Common Subsequence has no meaningful greedy ordering. Picking the first matching character doesn't guarantee the longest result. You need the full dynamic programming table to consider all alignment possibilities. Unlike shortest path problems where greedy works via Dijkstra's algorithm, subsequence problems require examining all possible alignments.

Edit Distance is another case where every choice cascades. Inserting a character now might save you two deletions later. There's no locally optimal edit operation. You need to compare all possible edit sequences through the DP approach.

Bellman-Ford shortest path is worth noting because it shows that even within the same problem category (shortest paths), greedy doesn't always work. When graphs have negative edge weights, Dijkstra's greedy algorithm fails and you need the dynamic programming based Bellman-Ford approach.

These five greedy vs DP problems taught me to stop and think before reaching for dynamic programming. Sometimes the simplest approach is the right one. My practice now is to always ask: "Can I sort this and scan once?" before building a DP table. More often than I expected, the answer is yes.

I've been working through pattern-based problem sets on Levelop, and this greedy algorithm vs dynamic programming distinction keeps coming up across different problem categories.