Rasool Abbas

Solving Task Scheduler with Math

05/24/2026

Over the past 4 months, I've been immersing myself in programming problems, challenges, and learning programming fundamentals at a deeper level. The TL;DR of why I am doing this is AI & I love learning.It has been an amazing journey so far. I've solved 100+ LeetCode problems and have emphasized learning by doing. I think I will write another blog post about this journey once I hit 150 problems solved, which is my goal.This problem stood out as being very interesting, I am not the first to do this but I was able to find a non-trivial solution to the following problem that is worth sharing:
Problem description for the task scheduler problem
Typically when I approach these problems, I refer to the knowledge I built already as my "toolbox", and I am reaching into my toolbox to grab the right tool to solve this problem given the constraints. I do this until I run into some wall or performance issue, then I try to fix and pivot. It's a very powerful learning experience.My initial thinking was to simulate the task scheduler processing the input with some kind of queue and process each CPU task, while counting the steps to return. But, I thought there might be some kind of way to mathematically calculate the answer. I just thought you must be able to calculate this answer given that some structure of CPU task list is forced.I wasn't actually very confident about that after reading the last sentence of the problem description: "Return the minimum number of CPU intervals required to complete all tasks". That sentence invalidated some of my thinking because it can usually mean specific kinds of algorithms would solve this problem (namely, dynamic programming) but it wasn't so clear.I went ahead with attempting a mathematical solution anyway hoping that if I was stumbling down the wrong path, I'll come back out with lots of lessons learned.

First steps

Alright, what is this problem actually asking us? Well, it seems simple, given some array of characters that represent CPU tasks, return the minimum amount of execution steps needed such that duplicate tasks are separated by at least n other tasks. Also, you can use an "idle" task to fill in gaps where necessary.So far it's not clear what the mathematical solution should be. Our goal though is to find a pattern that we can predict with math, so let's look at a few test cases. I always find that going through test cases and typing out my thoughts and state about the problem helps me reason through it much better.Running through the first sample test case:
test case 1
input: tasks = ["A", "A", "A", "B", "B", "B"], n = 2
output: 8
So each A and each B must be separated by at least 2 other tasks (which includes the "idle" task). Since we are looking for the minimum number of steps to complete the tasks, we can only separate duplicate tasks by 2 (the n value).For this specific test case, one solution can be:
test case 1 solution
["A", "B", "idle", "A", "B", "idle", "A", "B"]
Notice how each "A" and "B" are separated by 2 other unique instructions. Another solution can look like:
test case 1 solution alternative
["B", "A", "idle", "B", "A", "idle", "B", "A"]
The pattern stays the same, repeating tasks are separated by at least (and ideally, at most) n other tasks. Now, let's take a look at another test case where we don't have the same number of repeating tasks.
test case 2
input: tasks = ["A", "A", "A", "B", "B"], n = 2
output: 7
The clear solution for this is the following sequence:
test case 2 solution
["A", "B", "idle", "A", "B", "idle", "A"]
When I drew this solution, I stared at how this sequence looks and noticed there was a pattern in the sequence structure:
test case 2 pattern
["A", <>, <>, "A", <>, <>, "A"]
At this point I realized that it doesn't matter what other tasks are, the structure of the solution sequence is forced by the most frequent CPU task. For the first test case with the same amount of repeating tasks, the structure is still forced by the most frequent task (either "A" or "B" in the initial test case) but the amount remains the same.

The pattern

After seeing this pattern, I decided to denote t to represent the count of the most frequent repeating CPU task. The first derivation I came up with is below:
Minimum steps formula
A=(t-1)·(n+1)+1
Where:
t
The count of the most frequent CPU task
n
The cooling interval (minimum tasks between duplicates)
Let's break down this formula and visualize what's happening by first using the problem from earlier as an example:
test case
input: tasks = ["A", "A", "A", "B", "B"], n = 2
output: 7
t represents the count of the most frequent CPU task. In our case, that's A with a count of 3. So, why do we have (t - 1) in our formula? Let's remember back to the forced pattern of the answer for this example:
pattern
["A", <>, <>, "A", <>, <>, "A"]
Notice how only 2 blocks of A tasks are present in our forced structure with the 2 "anything" slots [<>, <>]. We're essentially subtracting 1 occurrence of the most frequent CPU task because the last most frequent CPU task will go at the end alone, without a cool down period.In other words, we have 2 occurrences of "A", <>, <> and one lone occurrence at the end of A.If we didn't have t - 1 in our formula, we would be building 3 blocks of"A", <>, <> which would generate a pattern of:
pattern without t - 1
["A", <>, <>, "A", <>, <>, "A", <>, <>]
Alright, so why do we have n + 1 then? Let's look at the example this way:
pattern with t - 1 only
["A", "A"]
The above shows taking the most frequent task A and subtracting its count by one (which ist - 1). Now we want to build the blocks of "A", <>, <>If we multiply n as is, we would get the following structure:
pattern with (t - 1) * n
["A", <>, "A", <>]
Notice that it's only 4 elements long because the calculation is (t - 1) * n which using our running example would be (3 - 1) * 2 = 4. In other words, n represents the recurring block size.From our visual example, we want the block size to be of size 3 which is "A", <>, <>It is true that from the input, n represents the cool down period, during which any tasks can run in the "anything" slots. However, in the mathematical representation, (n + 1) represents the recurring block size length, which is n "anything" slots plus the most frequent task.Putting those 2 pieces together, we have a formula that represents the following pattern:
pattern with (t - 1) * (n + 1)
["A", <>, <>, "A", <>, <>]
Now we are missing the last A task at the end, which is what the + 1 is for at the end of our formula.
pattern with (t - 1) * (n + 1) + 1
["A", <>, <>, "A", <>, <>, "A"]
This looked solid because we're methodically building the forced structure of the end result, however, I noticed that it does NOT work for the first example:
test case 1
input: tasks = ["A", "A", "A", "B", "B", "B"], n = 2
output: 8
I was thinking that because both A and B tasks had the same occurrence frequency, it wouldn't matter which one we chose as our most frequent task for the t variable. While that's true, the formula doesn't work, it's off by one:(t - 1) * (n + 1) + 1 would be (3 - 1) * (2 + 1) + 1 = 7 while the expected answer is 8. Let's take a look at the solution again for test case 1:
test case 1 solution
["A", "B", "idle", "A", "B", "idle", "A", "B"]
Let's just see the forced pattern we've been observing:
test case 1 pattern
["A", <>, <>, "A", <>, <>, "A", <>]
We're off by one because our formula is still generating the same pattern as the previous example:
test case 1 pattern from formula
["A", <>, <>, "A", <>, <>, "A"]
This is the right answer for test case 2, but the wrong answer for test case 1. That is because test case 1 has 2 tasks that tie for the most frequent task (A & B) and our formula does not support those kinds of test cases.The question is now how do we handle when more than 1 task ties for the most frequent task? Well, we know that if more than 1 task ties for the most frequent task, it doesn't matter which one we choose, any of them will force the same structure sequence.We also know from deriving the formula that we take t and then subtract one to get t - 1, then multiply by n + 1 to build blocks that make up the forced sequence. Finally, we attach the extra task we subtracted via t - 1 at the end to form a "tail" to the blocks.That approach works for tasks that only have 1 most frequent task, but when multiple tasks tie for the most frequent task, the "tail" is the size of how many tasks tie for the most frequent task.With this in mind, let's re-do our formula:
Minimum steps formula v2
A=(t-1)·(n+1)+c
Where:
t
The count of the most frequent CPU task
n
The cooling interval (minimum tasks between duplicates)
c
The count of tasks that tie for the most frequent task
Alright, let's write some code and submit this answer!
python
1class Solution:
2    def leastInterval(self, tasks: List[str], n: int) -> int:
3        freq = {}
4        t = 0
5        c = 0
6        
7        # building a frequency map of tasks
8        # and counting how many tasks tie for the most frequent task
9        for task in tasks:
10            freq[task] = freq.get(task, 0) + 1
11

12            if freq[task] > t:
13                t = freq[task]
14                c = 1
15            elif freq[task] == t:
16              c += 1
17        
18        return (t - 1) * (n + 1) + c
Well this is awkward, it works for the mentioned test cases but it fails for the following test case:
test case 3
input: tasks = ["A", "C", "A", "B", "D", "B"], n = 1
output: 6
Using our formula, (t - 1) * (n + 1) + c we would get (2 - 1) * (1 + 1) + 2 = 4 which is obviously wrong because our expected output is 6.Let's draw out one possible solution sequence:
test case 3 solution sequence
["A", "C", "A", "B", "D", "B"]
Interesting, it looks like this test case does not have any idle tasks in the solution sequence. In other words, due to the amount of distinct tasks, there is no forced structure that would otherwise exist with "idle" interlaced in the sequence. So what does that actually mean? Since there is no forced structure that we can build with blocks, we simply just arrange the tasks in some sequence that would suffice. This heavily depends on the input and some test cases might have multiple solutions, however, we don't really care about the sequence. The fact is, if there is no forced structure, our formula is going to underestimate. Furthermore, if there is no forced structure, the structure is just some variation of the input tasks. This means we can just pass in the length of the input tasks array if our formula is underestimating.Let's adjust our code now!
python
1class Solution:
2    def leastInterval(self, tasks: List[str], n: int) -> int:
3        freq = {}
4        t = 0
5        c = 0
6        
7        # building a frequency map of tasks
8        # and counting how many tasks tie for the most frequent task
9        for task in tasks:
10            freq[task] = freq.get(task, 0) + 1
11

12            if freq[task] > t:
13                t = freq[task]
14                c = 1
15            elif freq[task] == t:
16              c += 1
17        
18        # if our formula underestimates, the min time to execute
19        # all tasks is the amount of tasks!
20        return max((t - 1) * (n + 1) + c, len(tasks))
Alright, let's run it!
Submission for the task scheduler problem that passes

Conclusion

I still get stuck on LeetCode questions, however I am a bit surprised that I got on the thinking path for this unintuitive solution. The majority of the time I fall down the wrong path, write a lot of code, then realize I have some pieces correct but not as a whole. I think this is one of the rare times where going down an obscure thought process brought about a really nice geometric solution.Another interesting bit is that the discussion section of this problem is full of people advocating that this problem should be hard difficulty rather than medium, and I agree. This mathematical approach took me much more time than figuring out the main approach using a priority queue. However, sometimes the stars align and an unintuitive solution shows itself!