Minimum Number of Days to Make m Bouquets

Problem (yeniden ifade)

bloomDay[i], i. çiçeğin açtığı gündür. Bir buket, bitişik k açmış çiçek ister. m buketi mümkün kılan en küçük günü döndür; imkânsızsa -1.

Sezgi

Gün d işe yarıyorsa sonraki günler de yarar. d üzerinde binary search; gün d’de greedy buket say.

Yaklaşımlar

export function minDays(bloomDay: number[], m: number, k: number): number {
  if (BigInt(m) * BigInt(k) > BigInt(bloomDay.length)) return -1;
  let lo = Math.min(...bloomDay), hi = Math.max(...bloomDay);
  const ok = (day: number) => {
    let bouquets = 0, adj = 0;
    for (const d of bloomDay) {
      if (d <= day) { adj++; if (adj === k) { bouquets++; adj = 0; } }
      else adj = 0;
    }
    return bouquets >= m;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (ok(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

export function minDays(bloomDay: number[], m: number, k: number): number {
  if (BigInt(m) * BigInt(k) > BigInt(bloomDay.length)) return -1;
  let lo = Math.min(...bloomDay), hi = Math.max(...bloomDay);
  const ok = (day: number) => {
    let bouquets = 0, adj = 0;
    for (const d of bloomDay) {
      if (d <= day) { adj++; if (adj === k) { bouquets++; adj = 0; } }
      else adj = 0;
    }
    return bouquets >= m;
  };
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (ok(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}

Şablon bağlantısı

Çiçek açma gününe binary search; greedy k’lık bitişik gruplar fizibilite kontrolü.

Yansıma

• Gün d’de açmış bitişik k çiçekten m buket. feasible(d) bir geçişte buket sayar; araya açmamış çiçek kırar.
• m*k > n ise -1. lo = min(bloom), hi = max(bloom).
• Bitişik şartı olmasaydı bu hâlâ cevap üzerinde ikili arama olur muydu?