Classic Greedy Problems

Jr Codex DSA Notes

Level: Advanced Prerequisites: Chapter 4 Time to complete: ~30 minutes

Table of Contents

1. Jump Game
2. Merge Intervals
3. Fractional Knapsack
4. Try It Yourself
5. Summary & Next Steps

1. Jump Game

Problem: Given an array where each element represents the maximum jump length from that position, determine whether you can reach the last index starting from index 0.

Greedy strategy: Track the furthest index reachable so far. Scan left to right; if you ever reach a position beyond the furthest-reachable point before getting there, you're stuck.

def can_jump(nums):
    furthest_reachable = 0
 
    for i, num in enumerate(nums):
        if i > furthest_reachable:
            return False                          # can't even reach position i
        furthest_reachable = max(furthest_reachable, i + num)
 
    return True
    # O(n) time, O(1) space

Why greedy is safe here: at each position, the only thing that matters for the rest of the journey is how far you can reach, not which specific jump lengths got you there — so always keeping track of the maximum reachable index (rather than trying every path) loses no information relevant to future decisions. That's the greedy choice property from Chapter 4 holding.

2. Merge Intervals

Problem: Given a list of intervals, merge all overlapping intervals into their union.

Greedy strategy: Sort by start time; then walk through once, extending the current interval whenever the next one overlaps, or starting a new one otherwise.

def merge_intervals(intervals):
    if not intervals:
        return []
 
    intervals = sorted(intervals, key=lambda pair: pair[0])   # sort by START time
    merged = [intervals[0]]
 
    for start, end in intervals[1:]:
        last_start, last_end = merged[-1]
        if start <= last_end:                 # overlaps with the last merged interval
            merged[-1] = (last_start, max(last_end, end))
        else:
            merged.append((start, end))
 
    return merged
    # O(n log n) — dominated by the sort

This is structurally close to Activity Selection (Chapter 4, Section 3), but sorted by start rather than end time, since the goal here is "combine everything overlapping" rather than "pick the maximum count of non-overlapping ones."

3. Fractional Knapsack

Problem: Same setup as 0/1 Knapsack (Chapter 3) — items with weight and value, a capacity limit — but now you're allowed to take a fraction of an item.

Greedy strategy: Sort items by value-per-weight ratio, descending. Take whole items greedily until one doesn't fully fit, then take exactly the fraction of that item needed to fill the remaining capacity.

def fractional_knapsack(weights, values, capacity):
    items = sorted(zip(weights, values), key=lambda x: x[1] / x[0], reverse=True)
    total_value = 0.0
    remaining = capacity
 
    for weight, value in items:
        if weight <= remaining:
            total_value += value                       # take the whole item
            remaining -= weight
        else:
            fraction = remaining / weight
            total_value += value * fraction             # take a fraction
            break                                        # capacity is now full
    return total_value
    # O(n log n) — dominated by the sort

This is the crucial contrast with Chapter 4: for 0/1 Knapsack, the best-ratio-first greedy strategy was not guaranteed correct, because items are indivisible and an early pick can foreclose a better whole-item combination. Here, because fractions are allowed, there's no such foreclosure — if the best-ratio item doesn't fully fit, you simply take exactly the fraction that fits, and no better combination could possibly exist (any alternative allocation of the same capacity to lower-ratio items produces strictly less value per unit of capacity used). Allowing fractions is precisely what restores the greedy choice property that 0/1 Knapsack lacks.

4. Try It Yourself

Before continuing to Module 11, decide whether each is a greedy or DP problem, and implement it:

# (a) Given meeting times as (start, end) pairs, find the MINIMUM number
#     of meeting rooms required to hold all of them without conflicts.
 
# (b) Given an array of coin denominations that do NOT necessarily form a
#     "canonical" system (e.g. [1, 5, 10, 25] works greedily, but
#     [1, 3, 4] does not always), find the minimum coins to make a target
#     amount. Is greedy ("always take the largest coin that fits") safe here?
 
# (c) Given an array of positive integers, determine if you can partition
#     it into two subsets with equal sum.

5. Summary & Next Steps

Key Takeaways

• Jump Game and Merge Intervals both have the greedy choice property — tracking one running value (furthest reach, or the last merged interval) at each step never forecloses a better later decision.
• Fractional Knapsack is greedy-solvable precisely because fractions are allowed — the moment you require whole/indivisible choices (0/1 Knapsack, Chapter 3), that same greedy strategy stops being correct.
• The "Try It Yourself" coin-change variant is the clearest possible illustration from this module: the same-looking greedy strategy ("always take the largest that fits") is correct for some denominations and silently wrong for others — always verify against DP or brute force on small cases before trusting a greedy solution in an unfamiliar problem.

Concept Check

1. Why does Jump Game only need to track the single value "furthest reachable index," rather than every possible path?
2. What single change turns 0/1 Knapsack (not greedy-solvable) into Fractional Knapsack (greedy-solvable)?
3. For the coin-change "Try It Yourself" problem, why does greedy fail for [1, 3, 4] but typically succeed for real-world currency denominations like [1, 5, 10, 25]?

Next Module

→ Module 11: Interview Prep & Revision

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index