Greedy — The Complete Guide

function greedySortAndScan(items: Item[]): Result {
  // 1. Sort by the greedy criterion
  //    (end time, deadline, size, ratio — problem-specific)
  items.sort((a, b) => a.key - b.key);

  // 2. Greedy scan — process items in sorted order
  let result = initialValue;
  let state = initialState; // tracks what's been committed

  for (const item of items) {
    if (isCompatible(item, state)) {
      // Take this item (greedy choice)
      result = update(result, item);
      state = updateState(state, item);
    }
    // Skip incompatible items
  }

  return result;
}
// When to use: activity selection, non-overlapping intervals,
// assign cookies, minimum arrows to burst balloons,
// minimum number of platforms

function greedyExpansion(nums: number[]): Result {
  let currentEnd = 0;   // farthest we can reach with current jumps
  let farthest = 0;     // farthest we can reach overall
  let jumps = 0;        // number of jumps taken

  for (let i = 0; i < nums.length - 1; i++) {
    // Update the farthest reachable position
    farthest = Math.max(farthest, i + nums[i]);

    // When we've exhausted the current jump's range
    if (i === currentEnd) {
      jumps++;
      currentEnd = farthest;

      // Early exit if we can already reach the end
      if (currentEnd >= nums.length - 1) break;
    }
  }

  return jumps;
}
// When to use: Jump Game, Jump Game II, Video Stitching,
// minimum number of taps to water a garden

function greedyBothEnds(items: Item[]): Result {
  // Sort by one criterion (e.g., height descending, then k ascending)
  items.sort((a, b) => {
    if (a.primary !== b.primary) return b.primary - a.primary;
    return a.secondary - b.secondary;
  });

  // Greedy insertion — place each item at its correct position
  const result: Item[] = [];
  for (const item of items) {
    result.splice(item.position, 0, item);
  }

  return result;
}
// When to use: Queue Reconstruction by Height,
// Candy distribution, boats to save people

function greedyAccumulation(nums: number[]): Result {
  let result = 0;
  let runningState = 0;

  for (let i = 0; i < nums.length; i++) {
    // Update running state
    runningState += contribution(nums[i]);

    // Greedy decision based on current state
    if (runningState > 0) {
      result += runningState; // take the profit
      runningState = 0;       // reset
    }
    // Or: if runningState < 0, reset to 0 (Kadane's-style)
  }

  return result;
}
// When to use: Best Time to Buy and Sell Stock II,
// Gas Station, Maximum Subarray (Kadane's),
// Partition Labels

function jump(nums: number[]): number {
  let jumps = 0;
  let currentEnd = 0;  // end of current jump's range
  let farthest = 0;    // farthest reachable from current range

  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);

    if (i === currentEnd) {
      // We've explored all positions in the current jump
      jumps++;
      currentEnd = farthest;
    }
  }

  return jumps;
}
// Time: O(n), Space: O(1)
// Think of it as BFS by levels: each "jump" is a BFS level.
// At each level, we find the farthest reachable position.
// Greedy: always extend to the farthest point in the next level.

function partitionLabels(s: string): number[] {
  // Step 1: Record last occurrence of each character
  const lastIndex = new Map<string, number>();
  for (let i = 0; i < s.length; i++) {
    lastIndex.set(s[i], i);
  }

  // Step 2: Greedy scan — extend partition to cover all characters
  const result: number[] = [];
  let partitionEnd = 0;
  let partitionStart = 0;

  for (let i = 0; i < s.length; i++) {
    // The partition must extend to at least the last occurrence
    // of the current character
    partitionEnd = Math.max(partitionEnd, lastIndex.get(s[i])!);

    if (i === partitionEnd) {
      // All characters in this partition are fully contained
      result.push(partitionEnd - partitionStart + 1);
      partitionStart = i + 1;
    }
  }

  return result;
}
// Time: O(n), Space: O(1) (at most 26 characters)
// Greedy: extend the partition boundary to the farthest last-occurrence.
// When the current index reaches the boundary, we can safely cut.

function canCompleteCircuit(gas: number[], cost: number[]): number {
  let totalSurplus = 0;
  let currentSurplus = 0;
  let start = 0;

  for (let i = 0; i < gas.length; i++) {
    const net = gas[i] - cost[i];
    totalSurplus += net;
    currentSurplus += net;

    if (currentSurplus < 0) {
      // Can't start from any station before i+1
      start = i + 1;
      currentSurplus = 0;
    }
  }

  // If total gas >= total cost, a solution exists and it's 'start'
  return totalSurplus >= 0 ? start : -1;
}
// Time: O(n), Space: O(1)
// Greedy: if the running surplus goes negative at station i,
// no station from 'start' to 'i' can be the answer.
// Reset start to i+1 and continue.
// If totalSurplus >= 0, the last 'start' is guaranteed to work.

Activities: [[1,4], [3,5], [0,6], [5,7], [3,9], [5,9], [6,10], [8,11], [8,12], [2,14], [12,16]]

Step 1: Sort by end time
  → [[1,4], [3,5], [0,6], [5,7], [3,9], [5,9], [6,10], [8,11], [8,12], [2,14], [12,16]]

Step 2: Greedy scan (always pick earliest finish that doesn't overlap)
  Take [1,4]   → lastEnd = 4, count = 1
  Skip [3,5]   → 3 < 4 (overlaps)
  Skip [0,6]   → 0 < 4 (overlaps)
  Take [5,7]   → 5 ≥ 4 ✓ lastEnd = 7, count = 2
  Skip [3,9]   → 3 < 7 (overlaps)
  Skip [5,9]   → 5 < 7 (overlaps)
  Skip [6,10]  → 6 < 7 (overlaps)
  Take [8,11]  → 8 ≥ 7 ✓ lastEnd = 11, count = 3
  Skip [8,12]  → 8 < 11 (overlaps)
  Skip [2,14]  → 2 < 11 (overlaps)
  Take [12,16] → 12 ≥ 11 ✓ lastEnd = 16, count = 4

Answer: 4 activities — [1,4], [5,7], [8,11], [12,16]

Key: Sorting by end time ensures we always leave maximum room for future activities.

nums = [2, 3, 1, 1, 4]
Goal: reach index 4 in minimum jumps

jumps=0, currentEnd=0, farthest=0

i=0: farthest = max(0, 0+2) = 2
     i === currentEnd (0===0) → jumps=1, currentEnd=2
     "Jump 1 can reach indices 0-2"

i=1: farthest = max(2, 1+3) = 4
     i !== currentEnd (1≠2)

i=2: farthest = max(4, 2+1) = 4
     i === currentEnd (2===2) → jumps=2, currentEnd=4
     "Jump 2 can reach indices 0-4"
     currentEnd(4) >= nums.length-1(4) → we can stop!

Answer: 2 jumps

Visualization:
  Index:  0  1  2  3  4
  Value:  2  3  1  1  4
  Jump 1: [0──────2]        (from 0, reach up to index 2)
  Jump 2:    [1──────────4]  (from range [1,2], reach up to index 4)

Key: Each "jump" is like a BFS level. We explore all positions in the current
level and find the farthest reachable position for the next level.

gas  = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
net  = [-2, -2, -2, 3, 3]   (gas[i] - cost[i])

totalSurplus = -2 + -2 + -2 + 3 + 3 = 0 ≥ 0 → solution exists!

Greedy scan:
  i=0: currentSurplus = -2 < 0 → start=1, reset to 0
  i=1: currentSurplus = -2 < 0 → start=2, reset to 0
  i=2: currentSurplus = -2 < 0 → start=3, reset to 0
  i=3: currentSurplus = 3 ≥ 0 → keep going
  i=4: currentSurplus = 3+3 = 6 ≥ 0 → keep going

Answer: start = 3

Verification: Starting at station 3:
  Station 3: tank = 0 + 4 - 1 = 3
  Station 4: tank = 3 + 5 - 2 = 6
  Station 0: tank = 6 + 1 - 3 = 4
  Station 1: tank = 4 + 2 - 4 = 2
  Station 2: tank = 2 + 3 - 5 = 0 ✓ (made it back!)

Key: When surplus goes negative, no station in [start..i] can work.
The deficit must be covered by surplus from later stations.

Does the problem ask to maximize/minimize something by making sequential choices?
├── NO  → Greedy probably doesn't apply. Consider other patterns.
└── YES → Do choices interact? (Does picking item A affect the value of item B?)
          ├── YES → Use Dynamic Programming (choices are dependent)
          │         Examples: 0/1 Knapsack, Coin Change (non-standard), Edit Distance
          └── NO  → Can you find a counterexample that breaks the greedy choice?
                    ├── YES → Greedy fails. Use DP or Backtracking.
                    └── NO  → Greedy likely works! What's the greedy criterion?
                              ├── Intervals? → Sort by end time (scheduling) or start time (merging)
                              ├── Jumps/coverage? → Track farthest reachable (expansion)
                              ├── Assignment? → Sort both sides, match smallest to smallest
                              ├── Accumulation? → Track running surplus/profit
                              └── Digits/strings? → Use a stack, drop suboptimal elements