19. Greedy

TL;DR

At each step, commit the locally best choice that stays feasible; when the problem has matroid or exchange-argument structure, those local maxima align with the global optimum. The engineering core is sort or heap to expose the right candidate order, then one linear scan or repeat extract-min/max with feasibility checks (interval scheduling, Huffman-style merges, jump-game farthest reach).

Core Basics

• Object: local choices that stitch into global optimum via ordering or exchange argument.
• Proof burden: greedy is easy to code, hard to justify — prep one liner on why a swap cannot improve.
• Staff-level bar: pivot to DP when greedy certificate fails (“counterexample brainstorming”).

Recognition Cues

• Phrases: "maximum intervals non-overlapping", "minimum arrows / removals", "merge intervals", "jump to last index", "merge triplets", "hand of straights", "minimum meetings rooms" (heap variant), "activity selection".
• Shapes: intervals with start/end; array where picking leftmost feasible endpoint helps; combining smallest weights repeatedly; maintaining farthest index reachable in jumps.

Use-case Lens

• Best when: a local choice can be proven safe by exchange, staying-ahead, or interval ordering.
• Not for: choices that affect future feasibility in non-monotone ways; try DP/backtracking.
• Main invariant: after each local choice, there exists an optimal solution consistent with all choices made so far.
• Interview move: give the proof idea, not just the sort key.

Diagram

Step-by-step Visual

Example: Select the maximum non-overlapping intervals from [[1,3], [2,4], [3,5], [5,7]]. Greedy picks the interval that ends earliest.

Understanding

Exchange argument: swap any optimal solution into one that makes your greedy first step without worsening the objective (often after sorting by end time or by a dominance rule). Matroid / greedy on weighted bases (informally): independent-set problems where greedy-by-weight works. Farthest reach for jumps tracks the frontier of the next move layer—like BFS on implicit layers without storing the whole layer.

Generic Recipe

1. Identify what to optimize first—often sort key (earliest finish, largest edge for Kruskal's later graph context, left coordinate).
2. Scan with a feasibility invariant (last placed end time; merged interval boundary).
3. For heap selection, push candidates and pop when the invariant demands the next best (task scheduler, smallest range).
4. For jump games, track farthestReach from the current window of indices you can still step from.
5. If you cannot sketch an exchange proof sketch quickly, question greedy and reach for DP.

Complexity

• Time: dominated by sort (O(n \log n)) or heap ops (O(n \log n)); single scans (O(n)).
• Space: (O(1)) to (O(n)) for auxiliary arrays/heaps.

Memory Hooks

• Operational mantra: make the local choice only after naming the exchange, frontier, or cut that proves it safe.
• Anti-panic: do not trust the local choice until you can state the exchange, frontier, or cut argument.

Study Pattern (SDE3+)

• Recognition drill (10 min): tag prompts by exchange-sort, farthest frontier, interval scheduling, or feasibility range.
• Implementation sprint (25 min): code jump game and non-overlapping intervals; verbalize why the local choice is safe.
• Staff follow-up (10 min): produce a counterexample for a wrong greedy key and explain when DP is required.

Generic Code Template

Go

package main

import "sort"

type interval struct {
	start, end int
}

// Interval scheduling: maximize count — sort by end, greedy take if start >= lastEnd.
func maxNonOverlapping(intervals []interval) int {
	sort.Slice(intervals, func(left, right int) bool {
		return intervals[left].end < intervals[right].end
	})
	lastEnd := -1 << 30
	count := 0
	for _, current := range intervals {
		if current.start >= lastEnd {
			count++
			lastEnd = current.end
		}
	}
	return count
}

// Jump game I: can reach last index — greedy farthest reach.
func canJumpReachLast(steps []int) bool {
	farthest := 0
	for index := 0; index < len(steps); index++ {
		if index > farthest {
			return false
		}
		reach := index + steps[index]
		if reach > farthest {
			farthest = reach
		}
		if farthest >= len(steps)-1 {
			return true
		}
	}
	return farthest >= len(steps)-1
}

func main() {}

JavaScript

function maxNonOverlapping(intervals) {
  const sorted = [...intervals].sort((left, right) => left.end - right.end);
  let lastEnd = Number.NEGATIVE_INFINITY;
  let count = 0;
  for (const current of sorted) {
    if (current.start >= lastEnd) {
      count += 1;
      lastEnd = current.end;
    }
  }
  return count;
}

function canJumpReachLast(steps) {
  let farthest = 0;
  for (let index = 0; index < steps.length; index += 1) {
    if (index > farthest) {
      return false;
    }
    const reach = index + steps[index];
    if (reach > farthest) {
      farthest = reach;
    }
    if (farthest >= steps.length - 1) {
      return true;
    }
  }
  return farthest >= steps.length - 1;
}

Variants

• Sort + scan — merge intervals, non-overlapping count, partition labels (last occurrence sweep).
• Interval scheduling — earliest finishing next meeting; proof via exchange on interval with smallest end among compatible choices.
• Heap-based merging — Huffman (combine two smallest), task cooldown with ready times, smallest range covering k lists.
• Jump game farthest reach — single pass frontier; part II often greedy layer count / BFS-style.

Representative Problems

• 055. Jump Game — farthest reach
• 045. Jump Game II — greedy layers / minimum jumps
• 435. Non-overlapping Intervals — earliest end first

Anti-patterns

• Greedy on problems needing global lookahead without proof (classic traps → DP).
• Sorting intervals by start when end order is the correct greedy key for scheduling counts.
• Jump game variants: resetting farthest incorrectly per layer when problem asks minimum jumps (different loop structure).
• Huffman-style combine without a second heap refresh when costs update dynamically—keep heap consistent.