Greedy

Nasıl düşünülür

Her seçim için bir skor tanımla (en uzak erişim, en erken bitiş, en büyük kazanç). Sırala veya tara ki sonraki seçim açık olsun. Başka bir seçimi seninkisiyle değiştirmenin cevabı iyileştiremeyeceğini kanıtla (exchange).

Şablon şekilleri

Şekil	Temel hamle	Notlar
Jump erişim	En uzağı izle	i > far ise fail
Aralık seç	En erken bitiş önce	Maks örtüşmesiz
Benzin devresi	tank + start izle	total ≥ 0 ise benzersiz devre

Karmaşıklık temeli

Sıralama + tarama genelde O(n log n) + O(n), veya salt O(n).

Şablondan probleme

1. Yerel kuralı bir cümlede söyle.
2. Gerekirse sırala veya çalışan en iyiyi tut.
3. Bir kez tara, kuralı uygula; başarısızlık koşullarını izle.
4. Küçük bir karşı örnek denemesiyle sağduyu kontrolü.

/** 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;
}