Thinking in algorithms - A Different Way to Think About the Task Scheduler Problem

I recently came across the classic CPU Task Scheduler problem on HackerRank.

You are given an integer N representing the number of CPU tasks, an array of N uppercase characters where each character denotes a task, and an integer cooldown representing the cooldown period. Each task takes exactly one CPU interval to execute, and the same task cannot be executed again until at least cooldown intervals have passed.

During the cooldown, the CPU may execute a different task or remain idle if no valid task is available.

Your objective is to determine the minimum total number of CPU intervals (including idle intervals) required to complete all the tasks.

Example

Input:
tasks = AAABBB
cooldown = 2

Output:
8

One optimal schedule is:

A → B → idle → A → B → idle → A → B

If you've seen this problem before, you've probably also seen the elegant mathematical solution:

$$(f_{max}-1)(cooldown+1)+k$$

where:

• f_max = maximum frequency of any task
• k = number of tasks having frequency f_max

It's short, optimal, and interview-friendly.

But instead of asking "What's the formula?", I found myself wondering:

Can we actually build the schedule itself using simple Python primitives?

That curiosity led to a surprisingly elegant solution built around Counter, zip_longest, and chain.

---

The Core Idea

Imagine grouping identical tasks together.

aaaa
bbbbbbbb
cc
d
ee
ff
g
hhh
iiiiiiiiii
j

Instead of processing one task at a time, what if we interleave these groups?

Reading them row by row naturally spreads identical tasks apart.

For the input

aaaabbbbbbbbccdeeffghhhiiiiiiiiiij

we get

abcdefghij
abcefhi
abhi
abi
bi
bi
bi
bi
i
i

Notice how every repeated task automatically falls into a different row.

If a cooldown requires additional spacing, we simply pad the shorter rows with idle slots (_).

For example, with cooldown = 3:

abcdefghij
abcefhi
abhi
abi
_bi
_bi
_bi
_bi
__i
__i

Flattening these rows produces a valid execution schedule, and its length is exactly the answer we're looking for.

---

Step 1 — Count Task Frequencies

Let's begin with Python's Counter.

from collections import Counter

Counter(input_data)

which gives

{
    'a': 4,
    'b': 8,
    'c': 2,
    'd': 1,
    'e': 2,
    'f': 2,
    'g': 1,
    'h': 3,
    'i': 10,
    'j': 1
}

---

Step 2 — Build Character Sequences

Next, create one sequence for every distinct task.

sorted([k * v for k, v in Counter(input_data).items()])

Result:

[
    'aaaa',
    'bbbbbbbb',
    'cc',
    'd',
    'ee',
    'ff',
    'g',
    'hhh',
    'iiiiiiiiii',
    'j'
]

Let's call this list sequences.

---

Step 3 — Interleave the Sequences

Now comes the interesting part.

Python's itertools.zip_longest() reads every sequence in parallel.

from itertools import zip_longest

list(zip_longest(*sequences))

Result:

[
 ('a','b','c','d','e','f','g','h','i','j'),
 ('a','b','c',None,'e','f',None,'h','i',None),
 ('a','b',None,None,None,None,None,'h','i',None),
 ('a','b',None,None,None,None,None,None,'i',None),
 (None,'b',None,None,None,None,None,None,'i',None),
 (None,'b',None,None,None,None,None,None,'i',None),
 (None,'b',None,None,None,None,None,None,'i',None),
 (None,'b',None,None,None,None,None,None,'i',None),
 (None,None,None,None,None,None,None,None,'i',None),
 (None,None,None,None,None,None,None,None,'i',None)
]

Since not every sequence has the same length, zip_longest() fills the missing positions with None.

---

Step 4 — Remove Empty Slots

A simple list comprehension cleans things up.

intertwined = [
    [value for value in row if value]
    for row in zip_longest(*sequences)
]

Now we have

[
 ['a','b','c','d','e','f','g','h','i','j'],
 ['a','b','c','e','f','h','i'],
 ['a','b','h','i'],
 ['a','b','i'],
 ['b','i'],
 ['b','i'],
 ['b','i'],
 ['b','i'],
 ['i'],
 ['i']
]

Each row now contains at most one occurrence of every task.

---

Step 5 — Pad for Cooldown

If a row is shorter than the required cooldown spacing, prepend idle slots.

padded = [
    ['_'] * max(0, cooldown - len(group)) + group
    for group in intertwined
]

For cooldown = 3:

[
 ['a','b','c','d','e','f','g','h','i','j'],
 ['a','b','c','e','f','h','i'],
 ['a','b','h','i'],
 ['a','b','i'],
 ['_','b','i'],
 ['_','b','i'],
 ['_','b','i'],
 ['_','b','i'],
 ['_','_','i'],
 ['_','_','i']
]

The inserted _ values represent idle CPU intervals.

---

Step 6 — Flatten Everything

Finally, flatten the rows into a single schedule.

from itertools import chain

output = list(chain.from_iterable(padded))

Result:

[
 'a','b','c','d','e','f','g','h','i','j',
 'a','b','c','e','f','h','i',
 'a','b','h','i',
 'a','b','i',
 '_','b','i',
 '_','b','i',
 '_','b','i',
 '_','b','i',
 '_','_','i',
 '_','_','i'
]

The answer is simply

len(output)

🎉 Done!

---

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

where n is the total number of tasks.

---

Final Thoughts

Would I use this in a coding interview?

Probably not.

The mathematical formula is shorter, more elegant, and easier to justify under interview pressure.

But I enjoyed exploring the problem from a different angle. Rather than deriving the answer directly, this approach constructs the schedule itself using a handful of Python's built-in tools.

Sometimes the most enjoyable part of algorithmic problems isn't finding the shortest solution—it's discovering an unexpected perspective that makes the problem feel completely different.

If nothing else, this little experiment gave me a new appreciation for just how versatile zip_longest() can be.