Greedy algorithms & intervals

Commit to the locally-best move and never look back. When that works it's a sort plus one linear pass. The entire difficulty is epistemic: knowing when locally-best is also globally optimal.

Why this paradigm

A greedy algorithm builds a solution by repeatedly taking the choice that looks best right now, never reconsidering. When that works, it is gloriously simple and fast — usually just a sort plus one linear pass, O(n log n). The entire difficulty is epistemic: knowing when the locally-best choice is also globally optimal. Get that wrong and greedy silently returns wrong answers.

When is greedy correct? (two intuitions)

1. The exchange argument (the practical proof). Assume some optimal solution differs from the greedy one. Show you can swap greedy's choice into the optimal solution without making it worse. Repeat; the optimal morphs into greedy's solution while staying optimal → greedy is optimal. If you can construct such an exchange, greedy is safe. If you cannot, be suspicious.
2. Matroid / exchange structure (the theory). Problems whose feasible sets form a matroid are exactly the ones a greedy "take the best addable element" solves optimally (e.g. minimum spanning tree via Kruskal). You don't need the formalism in an interview, but the intuition — "any partial solution can always be extended toward the optimum by a local choice" — is the tell.

How to recognize a greedy problem

• "Maximum number of ...", "minimum number of ... to remove/cover", "can you reach ...", and the obvious local rule passes every small example you try.
• Sorting by some key makes the problem "fall out" in one pass.
• There's a clean argument that being greedy never hurts you later.

Intervals — a greedy sub-theme worth its own header

Interval problems (merge, insert, remove-fewest-to-deschedule, count meeting rooms) are a perennial interview favourite, and they all hinge on one decision: which key do you sort by?

The "earliest finish" exchange argument is the classic correctness proof for greedy. Picking the sort key correctly is 90% of solving an interval problem.

Jump game — LeetCode 55

Each nums[i] is the max jump length from index i. Can you reach the last index from index 0? Greedy: track the farthest index reachable so far. Sweep left to right; if the current index is beyond what's reachable, you're stuck. Otherwise extend reach. Why correct: if index i is reachable then so is every j < i, so it suffices to track a single "frontier" — no need to enumerate jump paths.

def can_jump(nums: List[int]) -> bool:
    farthest = 0
    for i, jump in enumerate(nums):
        if i > farthest:             # current index unreachable -> fail
            return False
        if i + jump > farthest:      # extend the frontier greedily
            farthest = i + jump
    return True

Gas station — LeetCode 134

Circular route; gas[i] available at station i, cost[i] to reach the next. Find the start index to complete the loop, or -1. Two facts: (1) if total gas < total cost, it's impossible; (2) otherwise a unique answer exists — track a running tank, and whenever it drops below 0 at station i, no start in [start..i] can work (each would run dry at or before i), so jump the candidate start to i+1 and reset. Why correct: the tank going negative at i proves every earlier start in the current window fails by i — a clean exchange-style argument.

def gas_station(gas: List[int], cost: List[int]) -> int:
    if sum(gas) < sum(cost):
        return -1                    # fact 1: globally infeasible
    start = 0
    tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:                 # window [start..i] can't be the start
            start = i + 1            # jump past the failure point
            tank = 0
    return start

Assign cookies — LeetCode 455

Child i is content if given a cookie of size ≥ greed[i]. Maximize content children. Greedy: sort both; feed the least-greedy child the smallest cookie that satisfies them. Why correct (exchange): "wasting" a big cookie on a low-greed child can only hurt, so always use the smallest sufficient cookie.

def assign_cookies(greed: List[int], sizes: List[int]) -> int:
    greed = sorted(greed)
    sizes = sorted(sizes)
    child = 0
    for s in sizes:                  # walk cookies smallest -> largest
        if child < len(greed) and s >= greed[child]:
            child += 1               # this cookie contents the current child
    return child

Partition labels — LeetCode 763

Cut s into the most parts so each letter appears in at most one part. Return the part sizes. Greedy: a part must extend to the last occurrence of every letter it contains. Precompute last[char]; sweep, expanding the part's end to max(end, last[c]); when the scan index reaches end, close the part. Why correct: closing earlier would split a letter across parts; closing later is never forced → the earliest valid cut is optimal for maximizing part count.

def partition_labels(s: str) -> List[int]:
    last = {c: i for i, c in enumerate(s)}   # last index of each char
    result: List[int] = []
    start = 0
    end = 0
    for i, c in enumerate(s):
        if last[c] > end:
            end = last[c]            # part must stretch to cover this char
        if i == end:                 # every char so far ends by here -> cut
            result.append(end - start + 1)
            start = i + 1
    return result

Intervals: merge — LeetCode 56 [sort by start]

Merge all overlapping intervals. Sort by start. Then sweep: if the next interval starts at/before the current merged interval's end, they overlap → extend the end; else emit and start fresh. Sorting by start guarantees that once a gap appears, nothing later can bridge it (later starts are even larger).

def merge_intervals(intervals: List[List[int]]) -> List[List[int]]:
    if not intervals:
        return []
    intervals = sorted(intervals, key=lambda iv: iv[0])   # SORT BY START
    merged = [intervals[0][:]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:           # overlap -> absorb
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])      # disjoint -> new interval
    return merged

Intervals: insert — LeetCode 57

Insert new into an already-sorted, non-overlapping list, merging as needed. Three phases exploiting the pre-sorted order (no re-sort needed): (1) emit all intervals ending strictly before new starts; (2) merge everything overlapping new into one widened interval; (3) emit the rest (strictly right).

def insert_interval(intervals: List[List[int]], new: List[int]) -> List[List[int]]:
    res: List[List[int]] = []
    i, n = 0, len(intervals)
    # phase 1: intervals entirely before new
    while i < n and intervals[i][1] < new[0]:
        res.append(intervals[i])
        i += 1
    # phase 2: overlapping -> merge into `new`
    new = 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)
    # phase 3: intervals entirely after new
    while i < n:
        res.append(intervals[i])
        i += 1
    return res

Intervals: non-overlapping — LeetCode 435 [sort by end]

Minimum number of intervals to remove so the rest don't overlap. Equivalent to: keep the maximum set of non-overlapping intervals (activity selection), then removals = total − kept. Sort by end. Greedily keep the interval that finishes earliest; it leaves the most room for the others. Drop any interval starting before the last kept end. Why correct (exchange argument): replacing the first kept interval in an optimal solution with the earliest-finishing one never reduces how many more you can fit → earliest-finish is always part of some optimum.

def erase_overlap_intervals(intervals: List[List[int]]) -> int:
    if not intervals:
        return 0
    intervals = sorted(intervals, key=lambda iv: iv[1])   # SORT BY END
    kept_end = intervals[0][1]
    kept = 1
    for start, end in intervals[1:]:
        if start >= kept_end:        # no overlap with the last kept -> keep it
            kept += 1
            kept_end = end
    return len(intervals) - kept     # the rest must be erased

Meeting rooms I — LeetCode 252 [sort by start]

Can one person attend all meetings (no two overlap)? Sort by start, then check adjacent pairs: any meeting starting before the previous one ends is a conflict.

def can_attend_meetings(intervals: List[List[int]]) -> bool:
    intervals = sorted(intervals, key=lambda iv: iv[0])   # SORT BY START
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False             # overlap -> impossible
    return True

Meeting rooms II — LeetCode 253 [sort by start + min-heap of end times]

Minimum number of rooms needed so no two simultaneous meetings share a room (= max number of meetings overlapping at any instant). Sort by start, keep a min-heap of end times of meetings currently using a room. For each meeting: if the earliest-ending room is free by its start, reuse it (pop); always push this meeting's end. The heap size is the rooms in use; its max over time is the answer. The heap lets us reuse the room that frees up soonest — the greedy choice.

import heapq

def min_meeting_rooms(intervals: List[List[int]]) -> int:
    if not intervals:
        return 0
    intervals = sorted(intervals, key=lambda iv: iv[0])   # SORT BY START
    heap: List[int] = []             # min-heap of end times of busy rooms
    rooms = 0
    for start, end in intervals:
        while heap and heap[0] <= start:
            heapq.heappop(heap)      # a room freed up before this meeting begins
        heapq.heappush(heap, end)    # occupy a room until `end`
        rooms = max(rooms, len(heap))
    return rooms

The greedy-fails contrast — coin change

To make the failure concrete: greedy coin change (biggest-first) is correct only for canonical coin systems. For {1,5,10,25} amount 30 it returns the optimal 2 coins (25+5). For {1,3,4} amount 6 it returns 3 coins (4+1+1) while the true optimum is 2 (3+3) — wrong. That is exactly why coin change needs DP (lesson 14).

def coin_change_greedy(coins: List[int], amount: int) -> int:
    coins = sorted(coins, reverse=True)
    count = 0
    for c in coins:
        if amount == 0:
            break
        take = amount // c
        count += take
        amount -= take * c
    return count if amount == 0 else -1