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).

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.

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Mental Model

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.

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.