Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumbinary-search-on-answer

Koko Eating Bananas

Problem (restated)

Koko has piles of bananas and h hours. She eats at speed k bananas/hour (ceil per pile). Find minimum k so she finishes within h hours.

Intuition

Higher k always finishes no later → monotonic. Binary search k in [1, max(pile)].

Approaches

Binary search on eating speed

Tested only

Time O(n log M)Space O(1)

Idea. lo=1, hi=max(piles). feasible(k)=sum(ceil(pile/k)) ≤ h. Find min k.

Walkthrough. piles=[3,6,7,11], h=8 → k=4.

Trade-offs. Must use integer ceil carefully to avoid floats: (pile + k - 1) / k.

Solution

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

Template connection

Binary search on answer with a linear feasibility check.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?