optimization – Proof : LeetCode Task Scheduler

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


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


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

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

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

  1. 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

  1. 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?

Thanks a lot!