DEV Community: Kushagra Mehrotra

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

Kushagra Mehrotra — Tue, 30 Jun 2026 20:41:29 +0000

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_{ma x} - 1) (coo l d o w n + 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.

A love letter to CAPS lock

Kushagra Mehrotra — Tue, 12 Mar 2024 01:23:48 +0000

In my childhood my favourite keys were Caps Lock, along with Num lock and Scroll Lock. It was because I could see a real-time impact by pressing them, that was the LED that lit in my keyboard indicating that the respective key was on. I used to pretend I was sitting in a control room preparing for a launch mission: "Num Lock On! Scroll Lock On!... Boosters starting!... Hatch closed!... Controls Online!... Heads-up display booted!... and Caps Lock On! ... Launching Satellite! (proceeds to press enter)". Those were fun times. (is it just me? or anyone else relates?)

Apart from imagining wild sci-fi fantasies, Caps-Lock also had a utility. I was no touch-typist back then, so it was pretty useful to turn on Caps-Lock AND GO FULL BURST MODE IN CAPITAL LETTERS WHEN WRITING HEADINGS IN MS-WORD.
One day I was at my friends house, I saw him touch-typing, and it was so cool... I was determined to learn it as well. There was one speciality in his way of touch-typing, that he didn't utilize Shift for capitalizing even a single letter. The way he did was when he had to capitalize a letter he tapped Caps Lock ON and then proceeded to type a letter and then instantly he would turn Caps Lock OFF. It was fascinating to watch him move his fingers so fluidly! Even though the way I was taught¹ to touch-type was using Shift key to capitalize--the normal way--I remained fascinated with his way of using Caps Lock, and this fascination led me to keep exploring new ways of moving my fingers over keyboard.

In the journey, I explored Dvorak keyboard layout, Colemak keyboard layout, and Qarg² keyboard layout--albeit on Android phone not on physical keyboard--~~and not only that but I also learnt to use mouse with left hand~~ but anyways... along the way I discovered the use of Sticky keys in Windows!
Yes! those pesky pop-ups that appear when you tap Shift key five times in succession. The way you use them is like a auto-turning-off Caps Lock, or like the Android keyboard's shift press, where you press Shift and then you can lift your finger-off the key and press another key. If the key is an alphabet key then the letter will be capitalized and proceeding keystrokes would be registered normally; if the key is any other key it would act like you hit hotkey combination: Shift + <key>.

Whether Sticky keys settings is On or Off, you can still use your Shift key as usual by pressing and holding it with other key in combination; but enabling Sticky keys unlocked a new power!
The mechanism of Sticky key is: if you press a modifier key once, it turns it on, if you press it twice it locks it in On mode, and when you press it third time it turns off the modifier.

Personally I find this useful when writing full PowerShell commands like: Get-ChildItem, Get-ItemProperty, Expand-Archive, Measure-Command, etc. With Sticky keys ON--these Pascal-case names don't break my typing flow now.

Be careful though! Sticky keys can lead to annoyance when you are not careful or it can even permanently delete an item which you wanted to trash it to your Recycle bin³.
If you proceed to try Sticky keys setting, then there will be many such annoyances in the beginning where you press Shift or even Ctrl key (Oh beware that Sticky keys settings are for all modifier keys: Shift, Ctrl, and Alt) and lift-off your finger thinking you are registering a simple keystroke and not a hotkey combination but you end-up with a mishit.

With Sticky keys I've attained a level of satisfaction with my fascination with typing. I wanted to run over my keyboard one finger at a time and I've found a way, now I don't need to stretch my little fingers to hit a hotkey, I simply type the hotkey without pressing-and-holding.

Wrapping up, this might not exactly be a "love letter" to CAPS Lock but it all started with it.

I learned it from Typing Trainer Online - 100% Free Online Typing Web Tutor! though at the time it was https://my.typingtrainer.com/ (which now redirects to the former link). ↩
Reference : Typewise - QWERTY Killer: How Typewise’s Novel Hexagon Keyboard App Is Replacing Legacy Smartphone Keyboards; and the app Typewise Custom Keyboard - Apps on Google Play ↩
Since pressing Shift+Del would permanently delete an item on windows, sometimes without even confirmation. ↩