So you're absolutely right Sahnawaz that because of the sorted function there should be an increased time complexity. However, if we look at what we do, we first iterate through the entire list to keep counts (O(n)). Then, we sort based on the values which 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. So instead of it being O(nlogn) its actually just O(n) ☺
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. 👌🏻
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 :)
Nw at all!!:) Backing up a bit in the video ( ~ @3:47) may help with this! We are discussing idle time; and n is a given input representing the cooling interval between the same tasks. Looking at the example in the beginning, where we had 3 A’s [our most common task/task associated with the max occurring number] and n = 2, we would total an idle of (max_occuring_number - 1) * n -> (3 - 1) * 2 -> 2 * 2 = 4. And we see that we did in fact have 4 idle times. However we are interested in finding the minimum number of intervals not idle times. But this is based off of the idle times/cooling intervals that we must include. In this case, we know that for each maximum occurring task, we want to have n cooling intervals before introducing that same task again. Therefore, after each single task [taking one interval] we have to have n more intervals before having the same task. So, that means we have 1 interval followed by n more or (n + 1) intervals for each time our most common occurring task is present up until the last one (as after the last one we don’t need anymore idle times since we don’t have anymore tasks). “Including the A’s” means that we want to consider the task AND the idle time of n that follows, not only the idle time in between => (n + 1, not only n). In this scenario, we will have our maximum occurring number of 3 plus the n idle times that have to follow for each but the last one; it would become (max_occuring_number - 1) * (n + 1) + counter -> (3 - 1) * (2 + 1) + 1 -> 2 * 3 + 1 = 7 and we can see that we used 7 intervals for that answer. (Counter was one because we only have one task, A that shows up the most number of times.) And if you have any other questions at all feel free to let me know!!
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!
Ty! That’s actually a question I’ve had myself - I’d say if you can’t solve it, watch the solution and after watching it write it up yourself! Since the questions are usually about the same topics and the underlying concepts are just recycled, the more you do (after knowing a solution or not) the better you’ll get. And I’m sure you’ll start noticing the approaches on your own as well!:)
Yes ofc!! So when we are trying to arrange the letters, if we have all the same letters, then we would have to put in idle times since we can’t have them next to each other. So in that scenario we find the maximum occurring number and do our calculations. However, if we have enough different letters than we would actually be able to have every single letter arranged without needing to interleave idle times. So if we had A, A, A, B, C, D, E, F, G, with an idle number = 2, then doing the max calculations, we would actually output 7, however, since we have enough unique numbers, we can actually just arrange all of them so they are all used once and output the true answer, the equivalent of their length = 9. Essentially, we want to see which case we will have. And since we don’t know, we need to check. If every number is able to fit between the max occurring ones (as their would-be idle times), then the output of that calculation would be greater than or equal to the len of the input. And this is because while they can fit in between, there is no guarantee that they fill up all the idle spots. If this is not the case, then the unique ones would tail at the end, even after fitting in between and therefore we would need the entire length of the input as seen in this example. I hope that clears things up! Lemme know if you have any other questions:)
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.
Yep! So n is the intervals or the idle spots, but this doesn't actually account for the tasks themselves just what the filler is. So if want to account for the total intervals, we want to include the task and the idles spots together. Backing up a bit in the video ( ~ @3:47) may help with this! We are discussing idle time; and n is a given input representing the cooling interval between the same tasks. Looking at the example in the beginning, where we had 3 A’s [our most common task/task associated with the max occurring number] and n = 2, we would total an idle of (max_occuring_number - 1) * n -> (3 - 1) * 2 -> 2 * 2 = 4. And we see that we did in fact have 4 idle times. However we are interested in finding the minimum number of intervals not idle times. But this is based off of the idle times/cooling intervals that we must include. In this case, we know that for each maximum occurring task, we want to have n cooling intervals before introducing that same task again. Therefore, after each single task [taking one interval] we have to have n more intervals before having the same task. So, that means we have 1 interval followed by n more or (n + 1) intervals for each time our most common occurring task is present up until the last one (as after the last one we don’t need anymore idle times since we don’t have anymore tasks). “Including the A’s” means that we want to consider the task AND the idle time of n that follows, not only the idle time in between => (n + 1, not only n). In this scenario, we will have our maximum occurring number of 3 plus the n idle times that have to follow for each but the last one; it would become (max_occuring_number - 1) * (n + 1) + counter -> (3 - 1) * (2 + 1) + 1 -> 2 * 3 + 1 = 7 and we can see that we used 7 intervals for that answer. (Counter was one because we only have one task, A that shows up the most number of times.)
So you're absolutely right that because of the sorted function there should be an increased time complexity. However, if we look at what we do, we first iterate through the entire list to keep counts (O(n)). Then, we sort based on the values which 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. So instead of it being O(nlogn) its actually just O(n). Hope this helps and let me know if you have any other doubts/questions!:)
Hi Deepti :) Thank you a lot for this explanation--so much clearer than the other Task Scheduler youtube video in Java (I actually think you should promote this video by posting a comment that's like "I have it explained in Python on my channel"). One question I had was that you say that the counter is equal to the number of max _occuring_number, yet in the example you had shown for A B C A B C D E F G, your counter that you added after was D E F G (I believe?) so it was 6 + 4 = 10. But if this is the case, doesn't the 4 come from D E F G which is not a max occurning number (they all contribute 1). So therefore, I was a bit confused because the max occuring number would be from A and B, which (when you go through your code), would make the counter only 2? So was a little confused on that logic, but thank you so much :-)
Hey Jessica! Thank you so so much!! And yes - you are absolutely correct. The counter would not hold in that scenario. I'm assuming you are referencing time ~5:40. So, in that scenario I am trying to display an instance in which the counter actually would not hold, which would lead us to explore the other option, of taking the max of the length of tasks. The reason we want to do that is if all of them not only fit perfectly between the max occurring ones, but also overflow. So, in the example with A B C A B C D E F G. We can see the following occurrences: A = 2, B = 2, C = 2, D = 1, E = 1, F = 1, G = 1. Here, the counter would equal 3 (A, B and C). And we can see, that if n = 2. We would have a total of 10. This is because we have more numbers than max idle spots to fit. So, not only do we completely fill out the idle spots that we got with the formula we derived earlier for intervals: (max_occuring_number - 1) * (n + 1) + counter, but we would go over since we have a lot of numbers that are not max occurring ones. In this case we then simply take the length of the task list provided to us and return that. So, when you say that it would not hold for this, you are right. This is really sound reasoning and exactly what prompts us to find the “actual counter value” for that case or see how many more to add on; and the easiest way to do that is to recognize there is not much of a need to actually count what we add to the end but just notice that that would imply filling in everything in between the max occurring numbers and then appending all those left over (there would be no idle time at all). So, that would just be all of the given inputs = len(tasks). And for that we find and return the maximum of either the intervals, or the length of tasks given to us! Great question Jessica and let me know if you have any other questions at all! Or if I should clarify or go into more detail for anything else! And once again thank you for your comment!
@@DEEPTITALESRA can we request some leetcode problem explaination vidoes? Or you can made some urself but kindly try to make one whose solution videos are not there or very less and not good. I really loved ur explaination
Yup! So 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 and 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). While we're on the topic of complexities, 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. Great question!! Let me know if you have anymore!:)
Thanks!! A lot more coming soon!:)) So heap is another approach that works - I'm assuming you're going to keep a max heap for the most frequently occurring letter - that works too! Just something to look out for - it may take more time as you would have to loop through and adjust the counts for the letters but that would depend on how exactly you're using heap!
I am not sure if this is the right approach to solve this or any coding interview question. This is a crammed up solution and unless you have a very good cramming skills, you will forget all these additions and multiplications in an actual interview. Also, if someone has not solved this problem before, can he really come up with this solution in an actual interview setting ? I doubt. A solution using max heap us much more intuitive and doable in the interview.
It's totally fine if you didn't get this solution! To me, this was the most intuitive way to solve it and therefore doable at first glance. It actually took me more time to think of max heap haha! But we all think of things differently and the more we practice, the more we can all explore new ideas! I agree though that it's not advisable to memorize or cram, which is why I make it a point to work through examples, describe my thinking process, and go over the logic I implement. Please let me know if anything wasn't clear, and I'll be more than happy to go over it! I hope you take away more than the math or the addition or the multiplication -- the underlying approach for this problem is actually super cool and fun! And as mentioned in a previous comment as well, max heap is def a valid solution. There are also other videos that solve this problem that way, so feel free to check those out too. At the very least, hopefully this video shines a light on a new approach and potentially proves useful for future problems in some shape or form! :)
this is so much simpler than Heap. All she is doing is after finding the most occurring element. For example for the question with n= 2 and [A, A, A, B, B, B]. A or B=3 is the max. After she is making groups of (3-1) * (length of each group) . ==> 2 groups * length of each group which is n+1 ( n + 1 because it is _, _, + 'A' = 3 spots.) = 6 For example, we think of it as being like this [A, _, _] [A, _, _] At the end we add the counter to that length. The counter represents the number of tasks with max occurrence. So for our example, we have A = 3 and B = 3, so we have counter = 2. Then we add that to 6 to become 8, which is the least number of intervals the CPU will take to finish all given tasks. [A, _, _] [A, _, _], A, B ==> Length is 8. The _ _ spots are filled with the other B's. If the question was [A, A, A, A, B, B] n =2 for example. [A, _ _] [A, , _], [A, _ _] ==> The two B's would fill out like this [A, B,_] [A, B, _], [A, _ _] and the one max (A) is added at the end . So result is [A, B _] [A, B, _], [A, _ _] A ==> length of 10. Just wanted to explain it to someone so that I would understand it as thoroughly as possible as well.
![Non-overlapping Intervals - LeetCode 435 - Python [O(nlogn) Time and O(1) Space!]](/img/n.gif)
Omg I just got a job because of this!
What?? How
It was sarcasm
Best and simplest solution i have seen . Thank you for this .
Thanks so much:)))
Thanks so much, Deepti. I'm going to go through all your videos now. Please keep on helping us out!!
Yes Adi def! A lot more videos coming out:)
I think, Time complexity is O(N+KlogK), because of sorted function
So you're absolutely right Sahnawaz that because of the sorted function there should be an increased time complexity. However, if we look at what we do, we first iterate through the entire list to keep counts (O(n)). Then, we sort based on the values which 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. So instead of it being O(nlogn) its actually just O(n) ☺
Your power of identifying patterns is astonishing!😃
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. 👌🏻
Thank you sm Raeven! So glad it was helpful- def going to be making more!:))
I know you have very few subscribers but your videos are awesome and you speak English very well. Please keep m aking them.
Aw thank u sm! More coming very soon!:)
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 :)
Thank you so much!!!!!:)
You make it so simple and easy to understand. Please continue making more videos like this. Appreciated!
Thank you!!:) Will do haha
Thank you for your excellent video! I finally understand the code, appreciated!
Yay love to hear that Hwajung!!:))
can't believe that i really found my dsa teacher!!
Aw happy to hear this Karthik!!☺
This is an amazing one!! Very easy to understand as well
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.
Thank you so much Neil!!:)
Walking through with some sample text inputs helped a lot! I couldn't understand the leetcode test inputs at first.
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"?
Nw at all!!:)
Backing up a bit in the video ( ~ @3:47) may help with this! We are discussing idle time; and n is a given input representing the cooling interval between the same tasks. Looking at the example in the beginning, where we had 3 A’s [our most common task/task associated with the max occurring number] and n = 2, we would total an idle of (max_occuring_number - 1) * n -> (3 - 1) * 2 -> 2 * 2 = 4. And we see that we did in fact have 4 idle times. However we are interested in finding the minimum number of intervals not idle times. But this is based off of the idle times/cooling intervals that we must include. In this case, we know that for each maximum occurring task, we want to have n cooling intervals before introducing that same task again. Therefore, after each single task [taking one interval] we have to have n more intervals before having the same task. So, that means we have 1 interval followed by n more or (n + 1) intervals for each time our most common occurring task is present up until the last one (as after the last one we don’t need anymore idle times since we don’t have anymore tasks).
“Including the A’s” means that we want to consider the task AND the idle time of n that follows, not only the idle time in between => (n + 1, not only n). In this scenario, we will have our maximum occurring number of 3 plus the n idle times that have to follow for each but the last one; it would become (max_occuring_number - 1) * (n + 1) + counter -> (3 - 1) * (2 + 1) + 1 -> 2 * 3 + 1 = 7 and we can see that we used 7 intervals for that answer. (Counter was one because we only have one task, A that shows up the most number of times.)
And if you have any other questions at all feel free to let me know!!
@@DEEPTITALESRA wow that makes so much sense!! thank you again, you're fantastic at explaining your solutions and clarifying questions!!
@@adebs Aw thank you so much!!
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!
Ty! That’s actually a question I’ve had myself - I’d say if you can’t solve it, watch the solution and after watching it write it up yourself! Since the questions are usually about the same topics and the underlying concepts are just recycled, the more you do (after knowing a solution or not) the better you’ll get. And I’m sure you’ll start noticing the approaches on your own as well!:)
@@DEEPTITALESRA I'll do that, thanks!!
Can I pursue masters in computer science after bachelors in Biotechnology
please continue making videos!!!
thanks @deepti . Can you tell me why you are using max with len(tasks)?
Yes ofc!! So when we are trying to arrange the letters, if we have all the same letters, then we would have to put in idle times since we can’t have them next to each other. So in that scenario we find the maximum occurring number and do our calculations. However, if we have enough different letters than we would actually be able to have every single letter arranged without needing to interleave idle times. So if we had A, A, A, B, C, D, E, F, G, with an idle number = 2, then doing the max calculations, we would actually output 7, however, since we have enough unique numbers, we can actually just arrange all of them so they are all used once and output the true answer, the equivalent of their length = 9. Essentially, we want to see which case we will have. And since we don’t know, we need to check. If every number is able to fit between the max occurring ones (as their would-be idle times), then the output of that calculation would be greater than or equal to the len of the input. And this is because while they can fit in between, there is no guarantee that they fill up all the idle spots. If this is not the case, then the unique ones would tail at the end, even after fitting in between and therefore we would need the entire length of the input as seen in this example.
I hope that clears things up! Lemme know if you have any other questions:)
@@DEEPTITALESRA thanks a lot Deepti for wonderful explanation .
Thank you so much! Very well explained!
Tyy Yida!!:)
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.
Yep! So n is the intervals or the idle spots, but this doesn't actually account for the tasks themselves just what the filler is. So if want to account for the total intervals, we want to include the task and the idles spots together.
Backing up a bit in the video ( ~ @3:47) may help with this! We are discussing idle time; and n is a given input representing the cooling interval between the same tasks. Looking at the example in the beginning, where we had 3 A’s [our most common task/task associated with the max occurring number] and n = 2, we would total an idle of (max_occuring_number - 1) * n -> (3 - 1) * 2 -> 2 * 2 = 4. And we see that we did in fact have 4 idle times. However we are interested in finding the minimum number of intervals not idle times. But this is based off of the idle times/cooling intervals that we must include. In this case, we know that for each maximum occurring task, we want to have n cooling intervals before introducing that same task again. Therefore, after each single task [taking one interval] we have to have n more intervals before having the same task. So, that means we have 1 interval followed by n more or (n + 1) intervals for each time our most common occurring task is present up until the last one (as after the last one we don’t need anymore idle times since we don’t have anymore tasks).
“Including the A’s” means that we want to consider the task AND the idle time of n that follows, not only the idle time in between => (n + 1, not only n). In this scenario, we will have our maximum occurring number of 3 plus the n idle times that have to follow for each but the last one; it would become (max_occuring_number - 1) * (n + 1) + counter -> (3 - 1) * (2 + 1) + 1 -> 2 * 3 + 1 = 7 and we can see that we used 7 intervals for that answer. (Counter was one because we only have one task, A that shows up the most number of times.)
@@DEEPTITALESRA Wow makes so sense!! Thank you so much for kindly explaining this details for me, Deepti! :))) I will visit again for sure!
James Kang Ofc!! Yay:)
Nice! But it's not O(n) because you need to sort values, that can be done at O(nlogn)
So you're absolutely right that because of the sorted function there should be an increased time complexity. However, if we look at what we do, we first iterate through the entire list to keep counts (O(n)). Then, we sort based on the values which 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. So instead of it being O(nlogn) its actually just O(n). Hope this helps and let me know if you have any other doubts/questions!:)
Hi Deepti :) Thank you a lot for this explanation--so much clearer than the other Task Scheduler youtube video in Java (I actually think you should promote this video by posting a comment that's like "I have it explained in Python on my channel"). One question I had was that you say that the counter is equal to the number of max _occuring_number, yet in the example you had shown for A B C A B C D E F G, your counter that you added after was D E F G (I believe?) so it was 6 + 4 = 10. But if this is the case, doesn't the 4 come from D E F G which is not a max occurning number (they all contribute 1). So therefore, I was a bit confused because the max occuring number would be from A and B, which (when you go through your code), would make the counter only 2? So was a little confused on that logic, but thank you so much :-)
Hey Jessica! Thank you so so much!! And yes - you are absolutely correct. The counter would not hold in that scenario. I'm assuming you are referencing time ~5:40. So, in that scenario I am trying to display an instance in which the counter actually would not hold, which would lead us to explore the other option, of taking the max of the length of tasks. The reason we want to do that is if all of them not only fit perfectly between the max occurring ones, but also overflow. So, in the example with A B C A B C D E F G. We can see the following occurrences: A = 2, B = 2, C = 2, D = 1, E = 1, F = 1, G = 1. Here, the counter would equal 3 (A, B and C). And we can see, that if n = 2. We would have a total of 10. This is because we have more numbers than max idle spots to fit. So, not only do we completely fill out the idle spots that we got with the formula we derived earlier for intervals: (max_occuring_number - 1) * (n + 1) + counter, but we would go over since we have a lot of numbers that are not max occurring ones. In this case we then simply take the length of the task list provided to us and return that. So, when you say that it would not hold for this, you are right. This is really sound reasoning and exactly what prompts us to find the “actual counter value” for that case or see how many more to add on; and the easiest way to do that is to recognize there is not much of a need to actually count what we add to the end but just notice that that would imply filling in everything in between the max occurring numbers and then appending all those left over (there would be no idle time at all). So, that would just be all of the given inputs = len(tasks). And for that we find and return the maximum of either the intervals, or the length of tasks given to us!
Great question Jessica and let me know if you have any other questions at all! Or if I should clarify or go into more detail for anything else!
And once again thank you for your comment!
@@DEEPTITALESRA no one gives that much detailed explaination . Thats so great of u
@@code7434 Thank you! Happy to help:)
@@DEEPTITALESRA can we request some leetcode problem explaination vidoes? Or you can made some urself but kindly try to make one whose solution videos are not there or very less and not good. I really loved ur explaination
Do you know what the time complexity is?
Yup! So 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 and 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).
While we're on the topic of complexities, 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.
Great question!! Let me know if you have anymore!:)
@@DEEPTITALESRA omg you're amazing, thank you for such an in-depth answer!!
@@adebs ofc! anytime!!
nicely explain thanks.
Happy to help Utkarsh!!:))
excellent video. Keep up the good work.
Thank you!:)
Great explanation, thanks!
tysm!!:)))
How about using heap?
Edit : Please continue making these videos!
Thanks!! A lot more coming soon!:))
So heap is another approach that works - I'm assuming you're going to keep a max heap for the most frequently occurring letter - that works too! Just something to look out for - it may take more time as you would have to loop through and adjust the counts for the letters but that would depend on how exactly you're using heap!
so, you didnt actually used the idle slots count ?
Correct! I wanted to use that to show how many slots we can fill in between!
are u from india?
amazing solution! thank you so much!
Damn I'm that dumb kid who did'nt get this out of everyone lmao
Wait nooo - you can def get it Arpit!!
Let me know which parts I can clarify further and/or explain better and I'll do it! :))
Great explanation!
Thank you!!:)
Very helpful !
["A","A","A","B","B","B"]
0
It is failing for this Test case : Can you please dry run for this
Just ran it right now and it correctly outputs 6, were you getting something else?
@@DEEPTITALESRA actually i forgot to take max so that caused issue ,sorry
good explanation
Thank you sm!!:)
😍😍 you are so beautiful
hahaha thank you Henok:)
Not python☹
I am not sure if this is the right approach to solve this or any coding interview question. This is a crammed up solution and unless you have a very good cramming skills, you will forget all these additions and multiplications in an actual interview. Also, if someone has not solved this problem before, can he really come up with this solution in an actual interview setting ? I doubt.
A solution using max heap us much more intuitive and doable in the interview.
It's totally fine if you didn't get this solution! To me, this was the most intuitive way to solve it and therefore doable at first glance. It actually took me more time to think of max heap haha! But we all think of things differently and the more we practice, the more we can all explore new ideas! I agree though that it's not advisable to memorize or cram, which is why I make it a point to work through examples, describe my thinking process, and go over the logic I implement. Please let me know if anything wasn't clear, and I'll be more than happy to go over it! I hope you take away more than the math or the addition or the multiplication -- the underlying approach for this problem is actually super cool and fun! And as mentioned in a previous comment as well, max heap is def a valid solution. There are also other videos that solve this problem that way, so feel free to check those out too.
At the very least, hopefully this video shines a light on a new approach and potentially proves useful for future problems in some shape or form! :)
this is so much simpler than Heap. All she is doing is after finding the most occurring element.
For example for the question with n= 2 and [A, A, A, B, B, B]. A or B=3 is the max.
After she is making groups of (3-1) * (length of each group) .
==> 2 groups * length of each group which is n+1 ( n + 1 because it is _, _, + 'A' = 3 spots.) = 6
For example, we think of it as being like this [A, _, _] [A, _, _]
At the end we add the counter to that length. The counter represents the number of tasks with max occurrence. So for our example, we have A = 3 and B = 3, so we have counter = 2. Then we add that to 6 to become 8, which is the least number of intervals the CPU will take to finish all given tasks.
[A, _, _] [A, _, _], A, B ==> Length is 8. The _ _ spots are filled with the other B's.
If the question was [A, A, A, A, B, B] n =2 for example.
[A, _ _] [A, , _], [A, _ _] ==> The two B's would fill out like this [A, B,_] [A, B, _], [A, _ _] and the one max (A) is added at the end .
So result is [A, B _] [A, B, _], [A, _ _] A ==> length of 10.
Just wanted to explain it to someone so that I would understand it as thoroughly as possible as well.
Thank you so much, Deepti. I'm going to go through all your videos now. Please keep on helping us out!!
Haha love that Kathik! And yes many more videos on the way:))