Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Greedy

Guide 5 of 6 · Path 5 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumgreedy

Task Scheduler

Problem (restated)

CPU tasks labeled A-Z. Same letter needs cooldown n between runs. Any order; idle allowed. Min total units of time.

Intuition

Most frequent task forces (maxf-1) gaps of length n. Fill gaps with other tasks; leftover idles pad the schedule.

Approaches

Idle slots from max frequency

Tested only
Time O(n)Space O(1)

Idea. idles = max(0, empty, available); answer = tasks + idles. Multiple max-freq tasks shrink gap width.

Walkthrough. tasks=AAABBB, n=2 → 8.

Trade-offs. Priority queue simulation is O(n log 26); formula is O(n).

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

Template connection

Greedy packing / frequency bottleneck.

Reflection