How do you solve the task scheduler problem, where the same task cannot run twice in a row?
You look at the task that happens the most often, because that task sets the shape of the schedule and the number of idle slots depends on it.
from collections import Counter
def least_interval(tasks):
counts = Counter(tasks)
most = max(counts.values())
number_of_most = len([c for c in counts.values() if c == most])
return max(len(tasks), (most - 1) * (number_of_most + 1) + number_of_most)
So how does it work? Let the most common task happen the most times, and let there be that many different tasks tied for that. The busiest task has to be separated from itself by at least one other task, so the schedule needs most minus one gaps, and each gap has to be at least as long as the number of tied tasks.
the tasks A A A B B C
the counts A:3, B:2, C:1
the most 3
the tied ones 1, which is just A
the gaps 3 - 1 = 2
the answer max(6, 2 * 2 + 1) = 6
And there is a second case. When there is only one kind of task then there are no gaps at all, because you cannot put a task next to itself but there is no other task to put there. So the answer is just the number of tasks. That is why the formula takes the bigger of the two numbers.
the tasks A A A A
the counts A:4
the most 4
the tied ones 1
the answer max(4, 3 * 2 + 1) = 7
and indeed you need A _ A _ A _ A
And the formula is (most - 1) * (tied + 1) + tied. The first part is the gaps between the rows of the schedule, and the last part is the final row with the tied tasks in it.
And the complexity is O of n for the time, where n is the number of tasks, because you count them and you go through the counts once more.
So the rule to remember is this. The number of idle slots comes from the most common task and the number of tasks tied with it.
The last question in this topic shows the idle slots on their own.