Task Scheduler

The problem

tasks is a list of capital letters. Each letter is one task to run, and equal letters are the same kind of task. A processor works in intervals: in each interval it runs one task or stays idle. You choose the order in which the tasks run. Two tasks of the same kind must have at least n other intervals between them, and those may hold other tasks or be idle. Return the smallest number of intervals, idle ones included, in which every task can be run. When n is 0, nothing ever has to wait.

What to write

function solve(tasks: string[], n: number): number

Input
tasks = ["A","A","A","B","B","B"]
n = 2

Output
8

Input
tasks = ["A","A","A","B","B","B"]
n = 0

Output
6

Constraints

Tasks use uppercase letters and n is nonnegative.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   You choose the order, so the order of tasks tells you nothing. Tasks with different letters never restrict each other: only copies of the same letter must be kept apart. And there are at most 26 different letters, however long the list is.

2. Hint 2: Ask a smaller question

   Suppose the list is only A, A, A and n is 2. Write the shortest schedule by hand. How many intervals does it take, and how many of them are left free for other tasks?

3. Hint 3: Name the pattern

   For a given n, the length of the schedule depends only on how many times each task appears, and most of all on the largest of those numbers. So start by counting the tasks, with a map from letter to count. This is frequency counting. Read the lesson on frequency counting.

4. Hint 4: State the invariant

   The task that appears most often sets a frame. Each of its copies except the last starts a block of n + 1 intervals: the copy, then n intervals for other tasks or idling. One more interval follows the last block for every task with that highest count. The schedule is never shorter than this frame.

5. Hint 5: Sketch the pseudocode

   Count each letter in a map. Let top be the largest count, and tied the number of letters that have that count. Let frame = (top - 1) × (n + 1) + tied. Return frame or the number of tasks, whichever is larger.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

The most frequent kind of task creates blocks of n + 1 intervals. Account for every kind tied at that highest count, then compare with the total number of tasks.

The slow way

Build the schedule one interval at a time. In each interval, run the task with the most copies left among those that are allowed to run, or stay idle if none is. This gives the right length, but it loops once for every interval, idle ones included: two A's with n = 1,000 take 1,002 rounds for a list of two tasks.

The insight

You only need the schedule's length, not the schedule. The task that appears most often forces a frame: each of its copies except the last starts a block of n + 1 intervals, the copy and n more. The other tasks drop into the free intervals of the blocks. If there are too many to fit, no interval stays idle and the length is the number of tasks.

Step by step

1. Count how many times each task appears. Only the number of copies of each task matters. The order of the list does not, because you choose the order in which the tasks run.
2. Find the highest count. The task with the most copies needs the most room, because every two of its copies must be kept apart. The schedule can never be shorter than the room that task needs.
3. Count how many tasks share the highest count. Tasks that tie for the highest count each have a last copy that must come after all the blocks. Each of those last copies needs an interval of its own there.
4. Measure the frame: the full blocks, then one interval per tied task. There is one block fewer than the highest count, because nothing has to follow a last copy. Each block is n + 1 intervals, and each task with the highest count adds one interval for its last copy.
5. The answer is the frame or the number of tasks, whichever is larger. With few other tasks, the frame has room for all of them and the frame is the answer. With many, they fill every free interval and stretch the blocks, so nothing is idle and each task takes one interval.

The same numbered steps are the comments in each solution.

function solve(tasks, n) {
  // 1. Count how many times each task appears
  const counts = new Map();
  for (const task of tasks) counts.set(task, (counts.get(task) || 0) + 1);
  // 2. Find the highest count
  // (The 0 covers an empty list, which has no counts.)
  const highest = Math.max(0, ...counts.values());
  // 3. Count how many tasks share the highest count
  const tied = [...counts.values()].filter((count) => count === highest).length;
  // 4. Measure the frame: the full blocks, then one interval per tied task
  const frame = (highest - 1) * (n + 1) + tied;
  // 5. The answer is the frame or the number of tasks, whichever is larger
  return Math.max(tasks.length, frame);
}

function solve(tasks: string[], n: number): number {
  // 1. Count how many times each task appears
  const counts = new Map<string, number>();
  for (const task of tasks) counts.set(task, (counts.get(task) || 0) + 1);
  // 2. Find the highest count
  // (The 0 covers an empty list, which has no counts.)
  const highest = Math.max(0, ...counts.values());
  // 3. Count how many tasks share the highest count
  const tied = [...counts.values()].filter((count) => count === highest).length;
  // 4. Measure the frame: the full blocks, then one interval per tied task
  const frame = (highest - 1) * (n + 1) + tied;
  // 5. The answer is the frame or the number of tasks, whichever is larger
  return Math.max(tasks.length, frame);
}

def solve(tasks, n):
    # 1. Count how many times each task appears
    counts = {}
    for task in tasks:
        counts[task] = counts.get(task, 0) + 1
    # 2. Find the highest count
    # (The default of 0 covers an empty list, which has no counts.)
    highest = max(counts.values(), default=0)
    # 3. Count how many tasks share the highest count
    tied = sum(1 for count in counts.values() if count == highest)
    # 4. Measure the frame: the full blocks, then one interval per tied task
    frame = (highest - 1) * (n + 1) + tied
    # 5. The answer is the frame or the number of tasks, whichever is larger
    return max(len(tasks), frame)

Example 1, traced

Input
tasks = ["A","A","A","B","B","B"]
n = 2

Output
8

Why it works

A task with the highest count cannot finish before the full blocks have passed, and the last copies of the tied tasks need separate intervals after those blocks. So no schedule is shorter than the frame, and none is shorter than the number of tasks. The larger of the two can always be reached: the other tasks go into the free intervals, or stretch the blocks.

Time and space

Time O(tasks.length), extra space O(26). Counting reads each task once. Finding the highest count and the tasks that share it looks at each different letter, and there are at most 26 of them. So the time grows with the number of tasks, and the map never holds more than 26 counts.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Add one interval for each task with the highest count, not a single one. With only 1 added, example 1 gives 7 instead of 8: A and B both need a place for their last copy.
• Compare the frame with the number of tasks. Without that, example 2 returns its frame, 4, although six tasks cannot fit into 4 intervals.
• A block is n + 1 intervals, not n: the copy itself takes an interval too. With blocks of n, example 1 gives 6 instead of 8.

Pattern

Frequency counting. Builds on Top K Frequent Elements.

Keep going