Task Scheduler

We’re given a character array, tasks, where each character represents a unique task. These tasks need to be performed by a single CPU, with each task taking one unit of time. The tasks can be performed in any order. At any given time, a CPU can either perform some task or stay idle.

We’re given a character array, tasks, where each character represents a unique task. These tasks need to be performed by a single CPU, with each task taking one unit of time. The tasks can be performed in any order. At any given time, a CPU can either perform some task or stay idle.

For the given tasks, we are also provided with a positive integer value, n, which represents the cooling period between any two identical tasks. This means that the CPU must wait for at least n units of time before it performs the same task again. For example, if we have the tasks [ A , B , A , C ] [A,B,A,C] and n = 2, then after performing the first A A task, the CPU will wait for at least 2 units of time to perform the second A A task. During these 2 units of time, the CPU can either perform some other task or stay idle.

Given the two input values, tasks and n, find the least number of units of time the CPU will take to perform the given tasks.

Task Scheduler

Constraints

• tasks.length can be from 1 to 1000.
• tasks only has uppercase English letters.
• n can be from 0 to 100.

Examples

Let's look at a few examples to understand the problem better.

Example 1

Input:

• Tasks: A, A, B, B
• n = 2

Schedule: A, B, Idle, A, B

Explanation: We scheduled tasks A and B this way to get the smallest possible total time.

Output: Units of time = 5

Example 2

Input:

• Tasks: A, A, A, B, B, C, C
• n = 3

Schedule: A, B, C, A, Idle, B, Idle, Idle, A

Explanation: We first scheduled all the A tasks, then all the B tasks, and lastly all the C tasks to reach the smallest possible total time.

Output: Units of time = 9

Example 3

Input:

• Tasks: A, A, B, C
• n = 0

Schedule: B, A, C, A

Note: Since n = 0, we can arrange these tasks in any order. For example: [A, B, C, A], [A, B, A, C], [B, C, A, A], [C, B, A, A], [A, A, C, B] — they would all work.

Explanation: Since n = 0, it has no effect on the CPU's processing time. So we can schedule the tasks in any way we like.

Output: Units of time = 4

Solution

This problem can seem confusing at first. But it becomes simple once we focus on what we actually need: the idle time.

If we find the idle time and add it to the total number of tasks, we get our answer.

Here is the formula we use:

• Max idle time: (maxFrequency - 1) * n
• Reducing idle time for each other task: previousIdleTime - Math.min(maxFrequency - 1, currentFrequency)

The idea is:

• We find the task that appears the most often. This is maxFrequency.
• Between each repeat of this most-frequent task, there are n open slots. This gives us our starting idle time.
• We then try to fill these open slots using the other tasks. Each other task can fill up to maxFrequency - 1 slots (since that's how many "gaps" exist).
• Whatever idle time is left over after filling with all other tasks is our real idle time. It cannot go below 0.
• Finally, we add this idle time to the total number of tasks to get our answer.

Solution Using Sorting

function leastTime(tasks, n) {
  const frequencies = new Map();
  for (const task of tasks) {
    frequencies.set(task, (frequencies.get(task) || 0) + 1);
  }

  const sortedFrequencies = Array.from(frequencies.entries()).sort((a, b) => a[1] - b[1]);
  const maxFreq = sortedFrequencies[sortedFrequencies.length - 1][1];
  sortedFrequencies.pop();

  let idleTime = (maxFreq - 1) * n;

  while (sortedFrequencies.length > 0 && idleTime > 0) {
    idleTime -= Math.min(maxFreq - 1, sortedFrequencies[sortedFrequencies.length - 1][1]);
    sortedFrequencies.pop();
  }

  idleTime = Math.max(0, idleTime);
  return tasks.length + idleTime;
}

Solution Using a Max Heap

We can also solve this using a max heap instead of sorting. This lets us always grab the task with the highest remaining frequency quickly.

class MaxHeap {
  constructor() {
    this.heap = [];
  }

  size() { return this.heap.length; }
  isEmpty() { return this.heap.length === 0; }
  peek() { return this.heap[0]; }

  push(val) {
    this.heap.push(val);
    this._bubbleUp(this.heap.length - 1);
  }

  pop() {
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._bubbleDown(0);
    }
    return top;
  }

  _bubbleUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.heap[parent] >= this.heap[i]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  _bubbleDown(i) {
    const n = this.heap.length;
    while (true) {
      const left = 2 * i + 1, right = 2 * i + 2;
      let largest = i;
      if (left < n && this.heap[left] > this.heap[largest]) largest = left;
      if (right < n && this.heap[right] > this.heap[largest]) largest = right;
      if (largest === i) break;
      [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
      i = largest;
    }
  }
}

function leastTime(tasks, n) {
  const frequencies = new MaxHeap();
  const tempfreq = new Map();

  for (const task of tasks) {
    tempfreq.set(task, (tempfreq.get(task) || 0) + 1);
  }

  const arr = Array.from(tempfreq.values());
  for (const count of arr) {
    frequencies.push(count);
  }

  const maxFreq = frequencies.pop();
  let idleTime = (maxFreq - 1) * n;

  while (!frequencies.isEmpty() && idleTime > 0) {
    idleTime -= Math.min(maxFreq - 1, frequencies.pop());
  }

  idleTime = Math.max(0, idleTime);
  return tasks.length + idleTime;
}