Task Scheduler

Medium

The problem

Each letter in tasks is a job that takes 1 time unit. The CPU can do one job per unit or sit idle. Two jobs with the same letter must have at least n units between them. Return the fewest time units needed to finish all jobs; jobs may be done in any order.

Example 1
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
One schedule is A B idle A B idle A B.
Example 2
Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
With no waiting required, every unit does a job.
Example 3
Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
The six As need gaps of two units, for example A B C A D E A F G A idle idle A idle idle A.

Limits

1 ≤ tasks.length ≤ 10,000
Tasks are uppercase letters A to Z
0 ≤ n ≤ 100

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Always do the task with the most remaining runs, but a task must cool down for n intervals after running.

The idea

Max-heap of counts plus a queue of (count, time it becomes available again). Each tick run the top task, push it into the cooldown queue, release finished cooldowns. (Math shortcut: (maxCount−1)·(n+1) + number of tasks with maxCount.)

Target: O(T log 26) time

Go function shape

func leastInterval(tasks []byte, n int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// LeastInterval: the most frequent task decides the length. Place it every n+1 slots; the other tasks fill the gaps.
// Frames: (maxCount-1) full frames of n+1 slots, plus a last partial row holding every task tied for the max.
// If there are so many tasks that no idle time is needed, the answer is simply len(tasks).
func LeastInterval(tasks []byte, n int) int {
	var counts [26]int
	maxCount := 0
	for _, t := range tasks {
		counts[t-'A']++
		maxCount = max(maxCount, counts[t-'A'])
	}
	tied := 0
	for _, c := range counts {
		if c == maxCount {
			tied++
		}
	}
	return max(len(tasks), (maxCount-1)*(n+1)+tied)
}

Read the lesson: Heap / Top-K