Task Scheduler - LeetCode 621 - Python [O(n) time and O(1) Space!]

Explaining how to solve Task Scheduler in Python - LeetCode 621!

(Typo @5:40: should be adding D E F G to the end for output = 10!)

The time complexity for this solution will be O(n). We first iterate through the entire list to keep counts (O(n)). Then, we sort based on the values which typically comes out to O(nlogn) BUT we know that we are only ever sorting 26 letters maximum, so we only need 26 elements to sort and so our n = 26. This makes sorting a constant time operation = 26log26 = constant number not dependent on n, therefore, O(1). After, we iterate again to count how many max values we have that are also our maximum, and this again should be order O(n), but we are only iterating over 26 elements, so we know our while loop will terminate after 26 elements since len(lst) is bounded by 26. And finally, we do constant time calculations, so our overall time complexity is just O(n).

Our space complexity is also O(1) since we only need a dictionary with 26 keys.
** We will never have more than 26 letters so the keys in our dictionary are bound by 26 and therefore so is the length of the lst we maintain.

Music: Bensound

Lemme know if y'all got questions/comments!!

[arko]

Best and simplest solution i have seen . Thank you for this .

[TheAprc]

Thanks so much, Deepti. I'm going to go through all your videos now. Please keep on helping us out!!

[adebs]

sorry I've asked commented so much, but at 4:38, could you explain why we multiply by n+1 instead of n and what you mean by "including the A's"?

[happyhacker]

Your power of identifying patterns is astonishing!😃

[raevenbauto]

The explanation here is really good compared to the top viewed solutions!! Please continue making the explanation visual it helps me a lot to visualize what is happening. 👌🏻

[elibaum]

I know you have very few subscribers but your videos are awesome and you speak English very well. Please keep m aking them.

[scoobyy]

This is an amazing one!! Very easy to understand as well

[sahnawazshaban]

I think, Time complexity is O(N+KlogK), because of sorted function

[renoseo]

best video and solution i've ever seen! there are people asking about using heap, but i feel like this is literally just using the property of max heap without actually using heapq. keep it up :)

[iei]

Thank you for your excellent video! I finally understand the code, appreciated!

[cheekyjay]

You make it so simple and easy to understand. Please continue making more videos like this. Appreciated!

[Ramentop]

Walking through with some sample text inputs helped a lot! I couldn't understand the leetcode test inputs at first.

[karthikreddy_tkr]

can't believe that i really found my dsa teacher!!

[neilpradhan]

The best video ever, thanks for this one, I spent long time trying to understand this no body explained it as good as you did.

[codedoctor]

thanks @deepti . Can you tell me why you are using max with len(tasks)?

[mushiewaffle]

Thanks for the explanation a lot better than the explanations on LeetCode. If we are not able to solve it on our own, do you recommend just watching the solution? Not sure if searching up the solution is helping me or not... thanks!

[yida]

Thank you so much! Very well explained!

[illachieveit]

Can I pursue masters in computer science after bachelors in Biotechnology

[jmskks]

Thank you so much it was very helpful!!
One quick question, what was the reason we added +1 in the formula of intervals? (n+1) You mentioned that +1 is coming from those A's but..humm. not sure how those A's made it +1. Could you please put just a little bit of detail on that? Thank you so much.

[mirazzaidi]

so, you didnt actually used the idle slots count ?