Task Scheduler

Problem (yeniden ifade)

A-Z etiketli CPU görevleri. Aynı harfin çalıştırmaları arasında n cooldown gerekir. Sıra serbest; idle serbest. Minimum toplam zaman birimi.

Sezgi

En sık görev (maxf-1) adet n uzunluğunda boşluk zorlar. Boşlukları diğer görevlerle doldur; kalan idle’lar çizelgeyi şişirir.

Yaklaşımlar

export function leastInterval(tasks: string[], n: number): number {
  const freq = Array(26).fill(0);
  let maxf = 0, maxCount = 0;
  for (const t of tasks) {
    const i = t.charCodeAt(0) - 65;
    freq[i]!++;
    if (freq[i]! > maxf) {
      maxf = freq[i]!;
      maxCount = 1;
    } else if (freq[i] === maxf) maxCount++;
  }
  const parts = maxf - 1;
  const partLen = n - (maxCount - 1);
  const empty = Math.max(0, parts * partLen);
  const available = tasks.length - maxf * maxCount;
  const idles = Math.max(0, empty - available);
  return tasks.length + idles;
}

export function leastInterval(tasks: string[], n: number): number {
  const freq = Array(26).fill(0);
  let maxf = 0, maxCount = 0;
  for (const t of tasks) {
    const i = t.charCodeAt(0) - 65;
    freq[i]!++;
    if (freq[i]! > maxf) {
      maxf = freq[i]!;
      maxCount = 1;
    } else if (freq[i] === maxf) maxCount++;
  }
  const parts = maxf - 1;
  const partLen = n - (maxCount - 1);
  const empty = Math.max(0, parts * partLen);
  const available = tasks.length - maxf * maxCount;
  const idles = Math.max(0, empty - available);
  return tasks.length + idles;
}

Şablon bağlantısı

Greedy paketleme / frekans darboğazı.

Yansıma

• En sık görev f, o sıklıkta count görev. Cevap max(uzunluk, (f-1)*(n+1) + count).
• n = 0 ise bekleme yok, cevap uzunluk. Tek görev 1.
• Aynı harf f kez, araya n boşluk. İkinci bir harf aynı sıklıktaysa count artar.