Welcome back.
In the previous video we have understood the question in detail.
Now let's get started with the approach that we can take to solve this question.
And for this, let's say this is the task array which is given to us.
And let's say n is given to be two units or two intervals.
Okay.
Now notice that this question is a question where the greedy approach works.
Well.
Now why is that the case?
Or what would be the thing that we greedily do at every step?
So the greedy choice or the greedy step that we take at every point would be to arrange the tasks with
the highest frequency first, and we keep doing that.
So once the task with the highest frequency is done, then we would go ahead and arrange the tasks with
the second highest frequency and it would go on in that manner.
Okay.
And again when we arrange the tasks with the highest frequency, we will arrange them in a manner that
they are separated by n intervals.
Okay.
Now let's take a look at how this would play out with this example over here, which is the example
given to us.
Okay.
So you can see over here that C is the task with the highest frequency which is equal to three.
And n in this case is equal to two.
So let's go ahead and arrange these three C's.
Such that they are separated by two intervals.
So that would be C.
And then we have two intervals and we have c.
And again we have two intervals.
And then we have again c okay.
Now the next highest item or the task over here is E which has a frequency of two.
So let's go ahead and arrange E over here so we can put E over here.
And we can put E over here.
And then we're just left with a okay.
And a can be kept either here or here.
Now let's say we keep it over here and we will be left with one empty slot.
So this would be the best way or the way with the minimum intervals to do all these tasks such that
the constraint is met.
Okay.
Now again you could do it in multiple ways.
For example, you could do it in this manner as well.
And you could put E over here.
And then let's say you put two spaces, you put E over here and let's say you put a over here.
But notice that this approach clearly requires more intervals or has more idle intervals or idle slots
than this approach.
Okay.
So this is the approach that minimizes the number of empty or idle slots.
And once we have this approach, you can see that we can easily identify the total number of intervals
required, which in this case is seven.
Okay.
Now let me make some space over here.
Now observe that seven in this case is just the sum of the total number of tasks and the number of empty
slots.
So in this case we have a total of six tasks.
And we have one empty slot.
And that's why the total intervals required is equal to seven okay.
Now this means that to solve this question we just need an approach to identify the number of empty
slots required or the minimum number of empty slots required.
Okay.
And we can identify that by taking the approach that we have discussed over here.
Now let's discuss this approach in a more systematic manner.
So the first thing that we did over here was we arranged the item with the highest frequency in a way
that it was separated by n intervals.
And when you do that, notice that two parts are formed over here, because in this case the highest
frequency was equal to three.
And because we don't need something over here.
So therefore there were two parts in between okay.
So the first step is to identify the number of parts between the highest frequency task.
Now in this case that was equal to two.
And you can get this two by just subtracting one from the frequency of the highest frequency task.
So the frequency in this case is equal to three.
And if you do three minus one that gives us two which is the number of parts between the highest frequency
task.
So this is the first step.
Now once we have identified this we can proceed to calculate the number of slots in the parts over here.
So there are two parts.
And notice that in each part in this case there are n intervals okay.
So you have n is equal to two.
That's why you have two slots over here.
And similarly you have two slots over here.
So the number of slots in these parts would be n multiplied by the number of parts which is equal to
two.
So the number of slots in the parts is just n into the number of parts.
And in this case that's two into two which is equal to four.
Now we can proceed to the next step which is to identify the remaining number of tasks which need to
be filled.
Notice that we have already filled this c, this c and this c in this arrangement.
So the remaining tasks in this case is three okay.
Now how do we identify this.
Now we can see that to identify that all that we need to do is we just need to subtract the frequency
of the highest frequency task, which is three from the total length of the tasks array, which in this
case is equal to six.
Okay.
So we just need to subtract three from six.
And that gives us the number of remaining tasks which in this case is equal to three itself which is
this task over here, this task over here and this task over here.
Okay.
So we have four slots over here.
And we have three tasks to be filled in these four slots, which means that once we are done with this
we will be left with four minus three empty slots which is equal to one.
Okay.
So we would have one empty slot or idle slot after we have filled these three tasks in these four slots.
And once we have identified this we can just add this to the length of the tasks to.
Find the solution to the problem, which in this case is equal to seven.
So this is the approach that we can take to solve this question.
But there is a special case also which we need to discuss.
Let's say that the tasks array which is given to us has two items or two tasks which have the highest
frequency.
For example, let's say the tasks array is c, c, c, e and b.
Okay.
Now over here notice that the task c has a frequency of three.
And the task E has a frequency of three okay.
And for this example let's say that it's given that n is equal to three or the intervals between two
identical tasks is equal to three.
Okay.
Now let's proceed and see whether our approach will work over here.
So as we've discussed what we would do is first we would take one of the tasks which has the highest
frequency and we will arrange it.
So let's say we go ahead and arrange the C's over here in a way that there are three intervals between
two respective C's.
So that would be this arrangement over here.
Okay.
Now in the previous discussion what we said was that in these positions.
We would try to fill the remaining tasks.
But over here, notice we can't do that.
Okay.
Notice that you can't fit three E's in these positions because again, between two E's you need three
intervals because n is equal to three okay.
So if you put one e over here, you can put the second e only over here.
And then notice you're not able to put the third e among these slots okay.
So this is the major difference which requires to do a slight tweak to the approach that we have discussed
in the previous example, which is this one over here okay.
So let's see how we can slightly modify the approach that we have discussed to accommodate this special
case.
So what we will do is we will go ahead and fill the other task which also has the highest frequency
in these positions over here.
Okay.
So we have one E over here.
We have one E over here and we have one E over here.
So in a way the tasks with the highest frequency are becoming one unit.
So we can consider that we are putting one unit over here, another unit over here and another unit
over here.
Okay.
And then let's see how we can proceed with these four steps that we had previously discussed.
So the first step is to identify the number of parts that are there.
And you can see that even in this example the number of parts is just the highest frequency minus one
which is three minus one which is equal to two.
The second step is to identify the number of slots that we have in these parts.
Okay.
And for that we just need to multiply the number of parts which is two with n minus the number of tasks
with the highest frequency minus one.
So this is a tweak okay.
Again multiplying this over here with the number of parts is pretty straightforward.
Because whatever we have over here we have that over here as well.
So this part is pretty straightforward.
But what about this over here.
Notice that from N which is three.
In this case we are subtracting one which is the number of tasks with highest frequency minus one.
So in this case we have two tasks which have the highest frequency.
And from this we are subtracting one to get one.
Now let's say we had one more task over here which is f f f.
We would place f over here, over here and over here.
And in this case this two would be three and three minus one would be two.
And when you do n minus two that would be three minus two which is equal to one.
And notice that's what is left in this section or in this part.
So that's why the number of slots in each part which is left is equal to n minus the number of tasks
with the highest frequency minus one.
In this case that's equal to two.
And then to identify the total number of slots which are available, we just multiply this two over
here with the number of parts that we have, which in this case is two itself.
So the number of slots which is available over here is two into two which is equal to four.
All right.
So that brings us to step number three which is to identify the number of remaining tasks.
And for this we just need to identify how many tasks are already filled which are the tasks which have
the highest frequency.
Okay.
So in this case we can see that the highest frequency is three.
And there are two such tasks.
So we have already filled three into two which is six tasks.
And the remaining tasks would be the total length of the tasks array minus six okay.
Which is in this case seven minus six which is equal to one.
And that brings us to the next step, which is to identify the number of empty slots that would remain.
So.
So far we have seen that there is just one task to be filled.
And we have also seen that we have four slots remaining.
Okay.
So the number of empty slots in this case would be four minus one which is equal to three.
So we'll have three empty slots.
And once we get this three the answer would be the length of the input tasks array, which in this case
is seven plus the number of idle or empty tasks which is equal to three.
So the answer would be seven plus three which is equal to ten.
And we can just return this.
So this is how we can solve this question.
And again notice it involves these four steps okay.
Whether it's having one task with the highest frequency or whether there are multiple tasks with the
highest frequency, we just need to follow these four steps to solve this question.
So to summarize remember.
To solve this question, we just need to do number of tasks plus number of empty slots in the best arrangement.
And we have discussed two examples to understand the approach we can take to solve this question.
And these were the examples.
So in this example there is just one task which has the highest frequency which is three.
And in this example there are two such tasks okay.
And there were four steps over here in the approach that we have discussed, which is to first identify
the number of parts and after that to identify the slots in the parts.
And then we would have to identify the remaining tasks to be placed in the slots.
And finally using this we would identify the number of empty or idle slots.
And once we have identified this, we can just solve the question by returning the length of the tasks
array plus the number of idle or empty slots.
Okay, now quickly going through these examples over here.
This is the highest frequency item which is a.
And over here we have two items or two tasks which have the highest frequency.
So in this case the number of items with the highest frequency is equal to two.
Okay.
Now to identify the number of parts as we have discussed, all that we need to do is we need to do highest
frequency minus one, which in both of the cases is equal to two.
Now to identify the slots in the parts, what we have to do over here was we had to multiply the number
of parts with n okay n is another input parameter for the question.
Let's say n is equal to two.
That could be the case okay.
So to identify the number of slots in the parts over here, we've seen that we can just do p into n.
But if there are more than one item with the highest frequency then this would be p into n minus the
number of items with the highest frequency minus one.
Okay, so that would be two minus one.
In this example, notice that if there is just one item with the highest frequency, this would be one
minus one and it would cancel out.
And this over here would just become p into n.
All right.
And in the next step we would just try to identify how many tasks are remaining to be filled in the
slots, which are in fact the tasks which don't have the highest frequency.
And for that we just need to subtract the number of highest frequency items from the total number of
tasks given.
So in this case that would be five minus three, and in this case that would be seven minus three into
two okay.
So that's pretty straightforward.
And once we have the number of remaining tasks to be filled we can identify the idle slots by doing
s minus t.
Okay.
So these are the steps that we have discussed in the examples which can be used to solve this question.
Now one more thing that you need to keep in mind is that the number of idle tasks should never be less
than zero.
So if there is a scenario like let's say you have a, a, b, b and you have c, d, so let's say this
is the input array and n is equal to one okay.
So you'd have to fill a, leave a space and fill a.
And then when it comes to B's you'd have to fill B over here.
And you can fill B over here.
And then when we take a look at the remaining tasks it would be these two.
But the slots are zero right.
So zero minus two would give you minus two.
But in that case you have to just take the number of slots which are idle as zero.
And in that case, notice that the best way of filling the tasks is putting C and D over here.
And in this case, the total number of intervals required is in fact the length of the tasks array itself.
So again, a quick side note over here, the number of empty or idle slots should never be less than
zero.
So if it goes less than zero you can just take it as zero.
So in other words we'll just take the maximum between zero and s minus t okay.
And we'll see this again when we discuss how we can code this solution.