Greedy

How to think about it

Identify a score for each choice (farthest reach, earliest finish, largest gain). Sort or scan so the next pick is obvious. Prove that swapping any other pick for yours cannot improve the answer (exchange argument).

Template shapes

Shape	Core move	Notes
Jump reach	Track farthest	Fail if i > far
Interval select	Earliest end first	Max non-overlap
Gas circuit	Track tank + start	Unique circuit if total ≥ 0

Complexity baseline

Often O(n log n) for sort + O(n) scan, or pure O(n).

From template to problem

1. State the local rule in one sentence.
2. Sort or maintain a running best if needed.
3. Scan once applying the rule; track failure conditions.
4. Sanity-check with a tiny counterexample attempt.

/** Greedy template: Jump Game (farthest reach). Track far; fail if i > far. */
export function canJump(nums: number[]): boolean {
  let far = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > far) return false;
    far = Math.max(far, i + nums[i]!);
    if (far >= nums.length - 1) return true;
  }
  return true;
}

/** Greedy template: Jump Game (farthest reach). Track far; fail if i > far. */
export function canJump(nums: number[]): boolean {
  let far = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > far) return false;
    far = Math.max(far, i + nums[i]!);
    if (far >= nums.length - 1) return true;
  }
  return true;
}