Task Scheduler - Leetcode 621 - Python

0:00 - Read the problem
4:05 - Intuition
6:52 - Explaining Solution
11:45 - Coding Solution

leetcode 621

#task #scheduler #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[harshvaghani]

Please tell me I'm not the only one who couldn't have figured this out without solution or this video!!

[RoninCunningham]

Not the hero we deserve, but the hero we need

[symbol]

After coming back to this video like 10 times over the course of a month or 2 (giving up constantly on this problem), I finally came back today, listened to you explain the solution, after you explained it I didn't watch the coding this time and just tried it myself and it made sense. Finally progress...

[sharwariphadnis]

This is probably one of the most intuitive solutions I have seen for the Task Scheduler problem. Keep up the great work!

[deathstrokebrucewayne]

Your content is just wow ! The best there exists..Crisp...precise yet detailed ! And directly goes in the mind :)

[b]

There are many high votes solutions in Leetcode, but I just can't understand the concept behind their fancy solution.
Fortunately, I found this great video and could nearly solve it by myself.
Thanks a lot.

[binay_krishn]

your explanation skills i found is bestest in the entire youtube

[josembass]

As always, great explanation. This was great to explain greedy algorithms.

I'm somewhat concerned that still I'm not be able to figure out this approaches without some hints.

[dilmurodabdusamadov]

Thank you! I'd never be able to come up with this solution myself during the interview.

[Grawlix]

Optimized the code some. We can sort a single time and then simply use a deque() to avoid repeatedly pushing/popping from heap. It also really simplifies the internals of the while loop, since we don't need to track both a heap and a queue.


def leastInterval(self, tasks: List[str], n: int) -> int:
if n == 0: return len(tasks)

# Sort the array in order of max frequency
count = Counter(tasks)
frequencies = list(count.values())


# For each frequency, associate it with the time at which it can be ran. Use +1 to offset 0-indexing
jobs = deque([i+1, j] for i, j in enumerate(frequencies))

# Start the time variable at 0, so once we enter the loop we will be at time '1'
# This allows us to directly return time at the end.
time = 0

while jobs:
time += 1
if time < jobs[0][0]:
# The next task is not yet ready to run (still on cooldown) so wait one unit of time
continue

# The task is ready to run, so pop from the queue* and adjust its frequency
cur_turn, cur_freq = jobs.popleft()
cur_freq -= 1
if cur_freq > 0:
jobs.append([cur_turn + n + 1, cur_freq])

return time

[ekhobbies]

the only time you need to idle cpu is when there is no enough smaller tasks to fill the gaps! There for the result would be the maximum of either the total number of tasks or (maxTask * (1 + idleTime) - idleTime + howManyTimesTheMaxIs repeated ! (tested it on leetcode and got accepted)

[Mohammad-woyi]

I think the total time complexity of the final code should be O(n * len(tasks)) since we are iterating over all time slots available. So if we have a task array of [A, A, A, A] then the total number of loops will equal to n * len(tasks).

[rafiparvez]

This is one of best explanations I found for the problem. Thank you NeetCode!

[AnkitaNallana]

This would be hard for me to come up with in an interview! Thanks so much for the explanation!

[HamzaKhan-kmyi]

Great explanation. In my opinion this is very close to HARD but definitely not MEDIUM.

[brianevans]

Sweet, this was my solution. Didn't see it in the official Leetcode solutions, but it made so much sense.

[Artem_S_tr]

Wow, this is a fairly complex problem, but the explanation is just brilliant and so easy to follow!

[n.h.son]

Thanks to you, from your drawing solution I can get to the coding solution pretty easily

[CarlJohnson-ivsn]

Man, this is so hard. I also saw a math or greedy solution in the solution section. Will I ever get a good job :'(

[XxMGxX]

I don't think you can say O(log26) for the maxHeap, since it's not just one appearance per letter, it is task.length < 10^4, so there could be 10^4 pops * idle queue