Greedy & Intervals

Local-optimal proofs, jump game, interval scheduling/merging.

greedy-intervals.mdreadme

15 — Greedy & Intervals

Neetcode Week 12b. Greedy = "make the locally best choice and never look back." It's faster than DP, but it only works when you can prove the local choice doesn't ruin the global solution. This file teaches you when greedy is safe and how to handle interval problems.

Table of Contents

  1. What greedy is
  2. How to prove a greedy is correct
  3. Pattern: Jump Game family
  4. Pattern: Gas Station
  5. Pattern: Interval scheduling
  6. Pattern: Merge intervals
  7. Pattern: Insert interval
  8. Pattern: Meeting rooms
  9. Walked-through problems
  10. Pitfalls
  11. Practice list

1. What greedy is

Greedy makes a sequence of decisions, each locally optimal, without backtracking. Compare:

ApproachStrategy
Brute forceTry every combination
DPTry every combination with caching
GreedyMake one guess per step; never reconsider

Greedy is fastest but riskiest — if your local rule is wrong, you produce a wrong answer.

When greedy works

A problem has a greedy structure if:

  1. Local optimal choices remain optimal globally (the greedy choice property).
  2. After making a choice, the remaining problem is structurally the same (the optimal substructure property).

(2) alone gives DP. (1) is what makes greedy correct.

Examples where greedy works

  • Sorting tasks by earliest finishing time → maximum non-overlapping intervals.
  • Picking largest coins first → optimal change for certain coin systems (US coins).
  • Sorting books by length → minimum sequential reading time.

Examples where greedy DOESN'T work

  • Coin change with arbitrary denominations: [1, 3, 4] and target 6. Greedy picks 4+1+1 = 3 coins; optimal is 3+3 = 2.
  • 0/1 knapsack: greedy by value-density doesn't always work.
  • Shortest path with negative weights: Dijkstra's greedy fails.

The DP/greedy distinction matters in interviews. Interviewers often ask "why did you pick greedy here? prove it."

2. How to prove a greedy is correct

Three common proof techniques:

Exchange argument

Suppose the optimal solution differs from the greedy choice at some step. Show that swapping greedy's choice into the optimal solution doesn't make it worse — therefore greedy ≤ optimal everywhere.

Greedy stays ahead

After every step, the greedy partial solution is at least as good as any other partial solution. Inductively, this extends to the final answer.

Matroid theory (advanced; rarely needed)

Some problems are formal matroids, which mathematically guarantee greedy works. Useful theory but overkill for interviews.

In interviews, prove with examples + an exchange argument. "If we don't pick the earliest-finishing meeting, we'd have to drop something later we could have kept — so picking earliest-finishing is at least as good."

3. Pattern: Jump Game family

Jump Game (Medium)

Each nums[i] is max jump length from i. Can you reach the last index?

Greedy: maintain the farthest reachable index. If at any point the current index > farthest, we're stuck.

def can_jump(nums):
    farthest = 0
    for i in range(len(nums)):
        if i > farthest: return False
        farthest = max(farthest, i + nums[i])
    return True

Why greedy is correct: if we can reach index i, we can extend reach to i + nums[i]. We don't need to remember which path got us here — just the max.

Jump Game II (Medium)

Minimum number of jumps to reach the last index.

Greedy: track the current jump's farthest range. When we exhaust it, we must take another jump.

def jump(nums):
    jumps = 0
    cur_end = 0
    farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:                                  # must commit to a jump
            jumps += 1
            cur_end = farthest
    return jumps

The implicit BFS-like structure: each jump opens up the next layer. We only count jumps when we cross from one layer to the next.

4. Pattern: Gas Station

Gas Station (Medium)

Circular route of gas stations. gas[i] available, cost[i] to next. Start somewhere, return to it. Find starting index, or -1 if impossible.

Insight 1: total gas < total cost → impossible. Insight 2: if we run out at station j starting from i, we can't start anywhere from i to j either. So start fresh from j+1.

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 is correct: if gas[i..j] is a deficit run, then any starting point in [i..j] is also doomed — so just skip to j+1.

5. Pattern: Interval scheduling

Given intervals [start, end], select maximum number of non-overlapping intervals.

Greedy: sort by end time, pick the earliest-ending. Then skip overlapping ones.

def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])
    count = 0
    last_end = float('-inf')
    for s, e in intervals:
        if s >= last_end:
            count += 1
            last_end = e
    return count

Why earliest-ending? Picking the interval that ends soonest leaves the most room for future picks. (Exchange argument: any other interval i₁ that ends later can be swapped with the earliest-ending one without losing scheduling capacity.)

Non-overlapping Intervals (Medium)

Minimum intervals to remove so the rest are non-overlapping.

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])
    last_end = float('-inf')
    kept = 0
    for s, e in intervals:
        if s >= last_end:
            kept += 1
            last_end = e
    return len(intervals) - kept

Same template; we count how many we can keep.

6. Pattern: Merge intervals

Given intervals, merge overlapping ones.

Greedy: sort by start. Walk through; merge into the last result if overlapping.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    res = [intervals[0]]
    for s, e in intervals[1:]:
        if s <= res[-1][1]:
            res[-1][1] = max(res[-1][1], e)               # merge
        else:
            res.append([s, e])
    return res

Trace [[1,3],[2,6],[8,10],[15,18]]:

sorted: [[1,3],[2,6],[8,10],[15,18]]
res = [[1,3]]
s=2: 2 ≤ 3 → merge → [[1,6]]
s=8: 8 > 6 → append → [[1,6],[8,10]]
s=15: 15 > 10 → append → [[1,6],[8,10],[15,18]]

Linear after sort, so O(n log n).

7. Pattern: Insert interval

Insert newInterval into a sorted list of non-overlapping intervals; merge as needed.

Strategy: three pointers — before-overlap, overlap-merge, after-overlap.

def insert(intervals, new):
    res = []
    i, n = 0, len(intervals)
    
    # 1. add all intervals ending before new starts
    while i < n and intervals[i][1] < new[0]:
        res.append(intervals[i]); i += 1
    
    # 2. merge overlapping into new
    while i < n and intervals[i][0] <= new[1]:
        new[0] = min(new[0], intervals[i][0])
        new[1] = max(new[1], intervals[i][1])
        i += 1
    res.append(new)
    
    # 3. add the rest
    while i < n:
        res.append(intervals[i]); i += 1
    
    return res

O(n).

8. Pattern: Meeting rooms

Meeting Rooms II (Medium)

n meetings with [start, end]. Minimum number of rooms?

Approach 1: chronological events.

Treat starts as +1, ends as -1. Sort events. Walk through, tracking concurrent meetings.

def min_meeting_rooms(intervals):
    events = []
    for s, e in intervals:
        events.append((s, 1))
        events.append((e, -1))
    events.sort()                                          # tie: -1 before +1 if same time? depends on definition
    cur = best = 0
    for _, delta in events:
        cur += delta
        best = max(best, cur)
    return best

Approach 2: heap. Sort meetings by start. Heap of end times. For each meeting, if earliest-ending finished before this one starts, reuse that room. Else allocate new.

import heapq

def min_meeting_rooms(intervals):
    intervals.sort(key=lambda x: x[0])
    heap = []
    for s, e in intervals:
        if heap and heap[0] <= s:
            heapq.heappop(heap)                            # room frees up
        heapq.heappush(heap, e)
    return len(heap)

The heap holds end times of currently-occupied rooms. Its size at the end = answer.

9. Walked-through problems

Hand of Straights (Medium)

Can you partition hand into groups of groupSize consecutive integers?

from collections import Counter
import heapq

def is_n_straight_hand(hand, group_size):
    if len(hand) % group_size: return False
    count = Counter(hand)
    h = list(count.keys())
    heapq.heapify(h)
    while h:
        smallest = h[0]
        for x in range(smallest, smallest + group_size):
            if count[x] == 0: return False
            count[x] -= 1
            if count[x] == 0:
                if x != h[0]: return False                 # must remove top
                heapq.heappop(h)
    return True

Greedy: always start the next group with the smallest remaining card. (Why? The smallest can only be the start of a group; if we don't use it now, we'll never be able to.)

Minimum Number of Arrows to Burst Balloons (Medium)

def find_min_arrow_shots(points):
    points.sort(key=lambda p: p[1])
    arrows = 1
    last_end = points[0][1]
    for s, e in points[1:]:
        if s > last_end:
            arrows += 1
            last_end = e
    return arrows

Same greedy as interval scheduling. Sort by end; shoot at the earliest-ending balloon's end.

10. Pitfalls

Greedy doesn't work

Always pause and ask: "is the local choice provably optimal?" If you can't articulate a reason in 30 seconds, it's probably DP. Time-box your greedy attempt.

Wrong sort key

Sorting by start vs end can change the answer entirely:

  • Maximum non-overlapping → sort by end.
  • Minimum meeting rooms (heap version) → sort by start.
  • Merge intervals → sort by start.

Tie-breaking on same time

In meeting rooms event-based version, an end-event and start-event at the same time: which first?

  • If problem says "rooms become available at the same time as next meeting starts," count end before start (no extra room needed).
  • Sort (time, delta) where delta = -1 (end) sorts before +1 (start) if same time.

Forgetting to update farthest

In Jump Game, the bug is forgetting farthest = max(farthest, i + nums[i]) — without max, you'd reset farthest each step.

Greedy on coin change with weird denominations

coins = [1, 3, 4], target = 6. Greedy picks 4+1+1 = 3 coins. DP picks 3+3 = 2. Always check.

Insert-interval boundary conditions

intervals[i][1] < new[0] (strict) vs ≤ (non-strict). For touching intervals like [1,2], [2,3], do they merge? Read the problem.

11. Practice list

#ProblemPatternDifficulty
53Maximum SubarrayGreedy / KadaneMedium
55Jump GameReachabilityMedium
45Jump Game IIBFS-flavoredMedium
134Gas StationSkip-deficitMedium
56Merge IntervalsMergeMedium
57Insert IntervalInsert + mergeMedium
435Non-overlapping IntervalsEarliest-end greedyMedium
252Meeting RoomsSort + check overlapEasy
253Meeting Rooms IIHeap or eventsMedium
846Hand of StraightsSmallest-first greedyMedium
452Min Arrows to Burst BalloonsEarliest-end greedyMedium
763Partition LabelsLast-occurrence greedyMedium

TL;DR ✅

  • Greedy works only when local choice is provably optimal. Prove with exchange or stays-ahead.
  • Interval scheduling = sort by end time, take earliest non-overlapping.
  • Merge intervals = sort by start, then walk + merge overlapping.
  • Meeting Rooms II = heap of end times (or event-sweep with +1/-1).
  • Jump Game uses farthest-reachable. Jump Game II counts layer transitions.
  • Gas Station: skip past any deficit run.
  • Pause and verify why greedy works before coding. If stuck → switch to DP.

Next: 16-bit-manipulation.md.

External resources

problems/7 entries
●main
UTF-8·typescript