How to understand the solution to Task Scheduler problem on LeetCode?

Question

LeetCode Task Scheduler problem is the following:

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

Return the least number of units of times that the CPU will take to finish all the given tasks.

Example 1:

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

Output: 8

Explanation:

A -> B -> idle -> A -> B -> idle -> A -> B There are at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2

Output: 16

Explanation:

One possible solution is A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

This is a solution I found:

 def leastInterval(self, tasks: List[str], l: int) -> int:
 freq = [0]*26
 maxOccurrence = 0
 
 for task in tasks:
 freq[ord(task) - ord('A')] +=1
 
 freq.sort(reverse=True)
 
 idleBlocks = freq[0] - 1
 idlesState = idleBlocks * n
 
 for i in range(1, 26):
 idlesState -= min(freq[i], idleBlocks)
 
 return len(tasks) + max(0, idlesState)

Basically, it works like this:

Given the tasks ["A","A","A","A","A","A","B","C","D","E","F","G"]

1. Sort the tasks by frequency descendingly

{ A: 6, B: 1, C: 1, D: 1, E: 1, F: 1, G: 1 }

2. We first place the most frequent character. All the spots between the same characters are first idle.

A _ _ A _ _ A _ _ A _ _ A _ _ A

3. We try to fill the remaining characters in the idleSpots using the sorted task array. (most frequent filled first)

A B C A D E A F G A _ _ A _ _ A

4. If the idleSpots < 0, we return the total number of tasks, else we return the total number of tasks + idleSpots.

I'm having issues proving this statement:

If the idleSpots < 0, we return the total number of tasks.

In other words, if we manage to fill all the idle spots between the most frequent character, why are we sure to complete all the tasks without complimentary idle tasks?

How come we can't we end up with a case like this

A X X A X X A B _ _ B _ _?

Where X represents a character such that the idle spots between all the As are filled.

Can you give me some hints?

Answer 1

When idleSpot (or, as in the code, idleState) is zero or negative, it means we have enough tasks other than A to fill the required minimum cooldown periods between A tasks.

Well, suppose BB are the overflowing tasks. Instead of appending them to the end of scheduling queue, we can just insert them, one right after each A. So instead of
$\quad$A X X A X X A B _ _ B _ _
we will have
$\quad$A B X X A B X X A.
Note that the cooldown periods between all existing tasks of the same type are at least as large as before. The cooldown periods between Bs are as long as the cooldown periods between As, so they are no shorter than the minimum as well.

If we have addition overflowing tasks, such as CC, then we can do the same thing, inserting them one right after each A. So we would have
$\quad$A C B X X A C B X X A.
Note that the cooldown periods between all existing tasks of the same type are at least as large as before. The cooldown periods between Cs are as long as the cooldown periods between As, so they are no shorter than the minimum as well.

And so on.

• desmond.belphegor: Thanks a lot! It's really clear!