Koko Eating Bananas

Problem (yeniden ifade)

Koko’nun piles muz yığınları ve h saati var. Saatlik k hızında yer; bir yığını bitirmek ceil(pile/k) saat sürer ve aynı anda tek yığın yer. Tüm yığınları h saat içinde bitiren en küçük k’yı döndür.

Sezgi

Daha yüksek k her zaman daha geç bitirmez → monotonik. k’yı [1, max(pile)] içinde ikili ara.

Yaklaşımlar

export function minEatingSpeed(piles: number[], h: number): number {
  let lo = 1, hi = Math.max(...piles);
  const feasible = (k: number) => {
    let hours = 0;
    for (const p of piles) hours += Math.ceil(p / k);
    return hours <= h;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (feasible(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

export function minEatingSpeed(piles: number[], h: number): number {
  let lo = 1, hi = Math.max(...piles);
  const feasible = (k: number) => {
    let hours = 0;
    for (const p of piles) hours += Math.ceil(p / k);
    return hours <= h;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (feasible(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Şablon bağlantısı

Doğrusal uygulanabilirlik kontrolüyle cevap üzerinde ikili arama.

Yansıma

• Daha hızlı yemek asla daha geç bitirmez → k üzerinde ikili arama. lo = 1, hi = max(piles) neden?
• ceil(pile/k) tamsayı: (pile + k - 1) / k. Float bölme hangi dilde yanlış yuvarlar?
• h, yığın sayısından küçükse imkânsız mı? (Problem h ≥ piles.length garantiler.)