Greedy Pattern

When to use Greedy

• The problem asks for the minimum or maximum of something that can be assembled from local choices (jumps, intervals, swaps).
• You can prove a swap argument: any optimal solution can be transformed into the greedy one without making it worse.
• Sorting the input by a meaningful key (deadline, end time, profit-to-weight ratio) makes the locally best choice obvious.
• The problem says 'find any valid', 'is it possible', or 'minimum number of operations' rather than 'count all ways'.
• Dynamic programming would solve it but the state-transition collapses to a single tracked variable (current reach, last end, running max).

Template

function greedy(items) {
  items.sort((a, b) => a.key - b.key);
  let result = 0;
  let frontier = 0;
  for (const item of items) {
    if (item.start > frontier) {
      return -1;
    }
    if (canTakeLocallyOptimal(item, frontier)) {
      result++;
      frontier = item.end;
    }
  }
  return result;
}

Common mistakes

• Applying greedy when the problem actually requires dynamic programming — failing to prove the greedy-choice property leads to subtle counterexamples on edge cases.
• Sorting by the wrong key. In Non-overlapping Intervals, sorting by start time misses optimal selections; sorting by end time is the canonical move.
• Resetting the running frontier (Gas Station's tank, Jump Game's reach) at the wrong moment, off-by-one on the index where you restart.
• Forgetting to short-circuit when the greedy step fails — Jump Game returns false the instant the frontier can't reach the next index.
• Greedy on Task Scheduler without using a max-heap or a frequency-count formula, causing TLE on large inputs.