1
00:00:00,080 --> 00:00:01,010
Welcome back.

2
00:00:01,010 --> 00:00:05,180
In the previous video we have understood the question in detail.

3
00:00:05,210 --> 00:00:09,650
Now let's get started with the approach that we can take to solve this question.

4
00:00:09,650 --> 00:00:14,090
And for this, let's say this is the task array which is given to us.

5
00:00:14,090 --> 00:00:17,750
And let's say n is given to be two units or two intervals.

6
00:00:17,750 --> 00:00:18,230
Okay.

7
00:00:18,230 --> 00:00:23,990
Now notice that this question is a question where the greedy approach works.

8
00:00:23,990 --> 00:00:24,560
Well.

9
00:00:24,560 --> 00:00:26,060
Now why is that the case?

10
00:00:26,060 --> 00:00:30,200
Or what would be the thing that we greedily do at every step?

11
00:00:30,200 --> 00:00:38,150
So the greedy choice or the greedy step that we take at every point would be to arrange the tasks with

12
00:00:38,150 --> 00:00:41,660
the highest frequency first, and we keep doing that.

13
00:00:41,660 --> 00:00:47,960
So once the task with the highest frequency is done, then we would go ahead and arrange the tasks with

14
00:00:47,960 --> 00:00:52,190
the second highest frequency and it would go on in that manner.

15
00:00:52,190 --> 00:00:52,550
Okay.

16
00:00:52,550 --> 00:00:58,550
And again when we arrange the tasks with the highest frequency, we will arrange them in a manner that

17
00:00:58,550 --> 00:01:01,430
they are separated by n intervals.

18
00:01:01,460 --> 00:01:01,940
Okay.

19
00:01:01,940 --> 00:01:07,850
Now let's take a look at how this would play out with this example over here, which is the example

20
00:01:07,850 --> 00:01:08,660
given to us.

21
00:01:08,690 --> 00:01:09,140
Okay.

22
00:01:09,140 --> 00:01:16,340
So you can see over here that C is the task with the highest frequency which is equal to three.

23
00:01:16,340 --> 00:01:19,730
And n in this case is equal to two.

24
00:01:19,730 --> 00:01:23,540
So let's go ahead and arrange these three C's.

25
00:01:24,410 --> 00:01:27,860
Such that they are separated by two intervals.

26
00:01:27,860 --> 00:01:29,600
So that would be C.

27
00:01:29,600 --> 00:01:32,240
And then we have two intervals and we have c.

28
00:01:32,270 --> 00:01:33,920
And again we have two intervals.

29
00:01:33,920 --> 00:01:36,320
And then we have again c okay.

30
00:01:36,320 --> 00:01:43,310
Now the next highest item or the task over here is E which has a frequency of two.

31
00:01:43,310 --> 00:01:47,270
So let's go ahead and arrange E over here so we can put E over here.

32
00:01:47,270 --> 00:01:49,220
And we can put E over here.

33
00:01:49,220 --> 00:01:51,800
And then we're just left with a okay.

34
00:01:51,800 --> 00:01:55,220
And a can be kept either here or here.

35
00:01:55,220 --> 00:01:59,870
Now let's say we keep it over here and we will be left with one empty slot.

36
00:01:59,870 --> 00:02:06,290
So this would be the best way or the way with the minimum intervals to do all these tasks such that

37
00:02:06,290 --> 00:02:07,610
the constraint is met.

38
00:02:07,610 --> 00:02:07,970
Okay.

39
00:02:07,970 --> 00:02:09,980
Now again you could do it in multiple ways.

40
00:02:09,980 --> 00:02:12,740
For example, you could do it in this manner as well.

41
00:02:13,310 --> 00:02:15,200
And you could put E over here.

42
00:02:15,200 --> 00:02:20,420
And then let's say you put two spaces, you put E over here and let's say you put a over here.

43
00:02:20,420 --> 00:02:28,430
But notice that this approach clearly requires more intervals or has more idle intervals or idle slots

44
00:02:28,430 --> 00:02:29,840
than this approach.

45
00:02:29,840 --> 00:02:30,200
Okay.

46
00:02:30,200 --> 00:02:35,300
So this is the approach that minimizes the number of empty or idle slots.

47
00:02:35,300 --> 00:02:42,410
And once we have this approach, you can see that we can easily identify the total number of intervals

48
00:02:42,410 --> 00:02:45,050
required, which in this case is seven.

49
00:02:45,050 --> 00:02:45,350
Okay.

50
00:02:45,350 --> 00:02:47,510
Now let me make some space over here.

51
00:02:47,510 --> 00:02:56,330
Now observe that seven in this case is just the sum of the total number of tasks and the number of empty

52
00:02:56,330 --> 00:02:56,990
slots.

53
00:02:56,990 --> 00:03:00,560
So in this case we have a total of six tasks.

54
00:03:00,560 --> 00:03:03,230
And we have one empty slot.

55
00:03:03,230 --> 00:03:08,180
And that's why the total intervals required is equal to seven okay.

56
00:03:08,180 --> 00:03:16,700
Now this means that to solve this question we just need an approach to identify the number of empty

57
00:03:16,700 --> 00:03:20,930
slots required or the minimum number of empty slots required.

58
00:03:20,930 --> 00:03:21,440
Okay.

59
00:03:21,440 --> 00:03:26,210
And we can identify that by taking the approach that we have discussed over here.

60
00:03:26,210 --> 00:03:30,230
Now let's discuss this approach in a more systematic manner.

61
00:03:30,230 --> 00:03:36,590
So the first thing that we did over here was we arranged the item with the highest frequency in a way

62
00:03:36,590 --> 00:03:39,590
that it was separated by n intervals.

63
00:03:39,590 --> 00:03:46,070
And when you do that, notice that two parts are formed over here, because in this case the highest

64
00:03:46,070 --> 00:03:48,290
frequency was equal to three.

65
00:03:48,290 --> 00:03:50,990
And because we don't need something over here.

66
00:03:50,990 --> 00:03:54,140
So therefore there were two parts in between okay.

67
00:03:54,140 --> 00:04:01,700
So the first step is to identify the number of parts between the highest frequency task.

68
00:04:01,700 --> 00:04:04,400
Now in this case that was equal to two.

69
00:04:04,400 --> 00:04:12,890
And you can get this two by just subtracting one from the frequency of the highest frequency task.

70
00:04:12,890 --> 00:04:15,920
So the frequency in this case is equal to three.

71
00:04:15,920 --> 00:04:23,150
And if you do three minus one that gives us two which is the number of parts between the highest frequency

72
00:04:23,150 --> 00:04:23,690
task.

73
00:04:23,690 --> 00:04:25,130
So this is the first step.

74
00:04:25,130 --> 00:04:32,990
Now once we have identified this we can proceed to calculate the number of slots in the parts over here.

75
00:04:32,990 --> 00:04:34,490
So there are two parts.

76
00:04:34,490 --> 00:04:40,340
And notice that in each part in this case there are n intervals okay.

77
00:04:40,340 --> 00:04:41,750
So you have n is equal to two.

78
00:04:41,750 --> 00:04:43,610
That's why you have two slots over here.

79
00:04:43,610 --> 00:04:46,190
And similarly you have two slots over here.

80
00:04:46,190 --> 00:04:54,050
So the number of slots in these parts would be n multiplied by the number of parts which is equal to

81
00:04:54,050 --> 00:04:54,500
two.

82
00:04:54,500 --> 00:04:59,480
So the number of slots in the parts is just n into the number of parts.

83
00:04:59,480 --> 00:05:03,950
And in this case that's two into two which is equal to four.

84
00:05:03,950 --> 00:05:11,510
Now we can proceed to the next step which is to identify the remaining number of tasks which need to

85
00:05:11,510 --> 00:05:12,140
be filled.

86
00:05:12,140 --> 00:05:17,450
Notice that we have already filled this c, this c and this c in this arrangement.

87
00:05:17,450 --> 00:05:21,230
So the remaining tasks in this case is three okay.

88
00:05:21,230 --> 00:05:23,150
Now how do we identify this.

89
00:05:23,150 --> 00:05:30,170
Now we can see that to identify that all that we need to do is we just need to subtract the frequency

90
00:05:30,170 --> 00:05:37,280
of the highest frequency task, which is three from the total length of the tasks array, which in this

91
00:05:37,280 --> 00:05:39,080
case is equal to six.

92
00:05:39,080 --> 00:05:39,470
Okay.

93
00:05:39,470 --> 00:05:42,890
So we just need to subtract three from six.

94
00:05:42,890 --> 00:05:49,250
And that gives us the number of remaining tasks which in this case is equal to three itself which is

95
00:05:49,250 --> 00:05:53,600
this task over here, this task over here and this task over here.

96
00:05:53,600 --> 00:05:53,990
Okay.

97
00:05:53,990 --> 00:05:56,660
So we have four slots over here.

98
00:05:57,260 --> 00:06:04,040
And we have three tasks to be filled in these four slots, which means that once we are done with this

99
00:06:04,040 --> 00:06:09,710
we will be left with four minus three empty slots which is equal to one.

100
00:06:09,710 --> 00:06:10,070
Okay.

101
00:06:10,070 --> 00:06:17,510
So we would have one empty slot or idle slot after we have filled these three tasks in these four slots.

102
00:06:17,510 --> 00:06:23,150
And once we have identified this we can just add this to the length of the tasks to.

103
00:06:23,290 --> 00:06:27,640
Find the solution to the problem, which in this case is equal to seven.

104
00:06:27,640 --> 00:06:31,150
So this is the approach that we can take to solve this question.

105
00:06:31,150 --> 00:06:34,780
But there is a special case also which we need to discuss.

106
00:06:34,900 --> 00:06:42,670
Let's say that the tasks array which is given to us has two items or two tasks which have the highest

107
00:06:42,670 --> 00:06:43,450
frequency.

108
00:06:43,450 --> 00:06:49,600
For example, let's say the tasks array is c, c, c, e and b.

109
00:06:49,660 --> 00:06:50,440
Okay.

110
00:06:50,440 --> 00:06:55,630
Now over here notice that the task c has a frequency of three.

111
00:06:55,630 --> 00:06:59,980
And the task E has a frequency of three okay.

112
00:06:59,980 --> 00:07:06,760
And for this example let's say that it's given that n is equal to three or the intervals between two

113
00:07:06,760 --> 00:07:08,890
identical tasks is equal to three.

114
00:07:08,890 --> 00:07:09,280
Okay.

115
00:07:09,280 --> 00:07:13,510
Now let's proceed and see whether our approach will work over here.

116
00:07:13,510 --> 00:07:19,180
So as we've discussed what we would do is first we would take one of the tasks which has the highest

117
00:07:19,180 --> 00:07:21,130
frequency and we will arrange it.

118
00:07:21,130 --> 00:07:28,420
So let's say we go ahead and arrange the C's over here in a way that there are three intervals between

119
00:07:28,420 --> 00:07:29,800
two respective C's.

120
00:07:29,800 --> 00:07:31,750
So that would be this arrangement over here.

121
00:07:31,750 --> 00:07:32,230
Okay.

122
00:07:32,230 --> 00:07:37,240
Now in the previous discussion what we said was that in these positions.

123
00:07:38,010 --> 00:07:40,710
We would try to fill the remaining tasks.

124
00:07:40,710 --> 00:07:43,590
But over here, notice we can't do that.

125
00:07:43,590 --> 00:07:43,950
Okay.

126
00:07:43,980 --> 00:07:52,740
Notice that you can't fit three E's in these positions because again, between two E's you need three

127
00:07:52,740 --> 00:07:54,930
intervals because n is equal to three okay.

128
00:07:54,930 --> 00:08:00,240
So if you put one e over here, you can put the second e only over here.

129
00:08:00,240 --> 00:08:06,240
And then notice you're not able to put the third e among these slots okay.

130
00:08:06,240 --> 00:08:13,830
So this is the major difference which requires to do a slight tweak to the approach that we have discussed

131
00:08:13,830 --> 00:08:17,160
in the previous example, which is this one over here okay.

132
00:08:17,160 --> 00:08:23,640
So let's see how we can slightly modify the approach that we have discussed to accommodate this special

133
00:08:23,640 --> 00:08:24,120
case.

134
00:08:24,120 --> 00:08:31,380
So what we will do is we will go ahead and fill the other task which also has the highest frequency

135
00:08:31,380 --> 00:08:33,150
in these positions over here.

136
00:08:33,150 --> 00:08:33,510
Okay.

137
00:08:33,510 --> 00:08:35,100
So we have one E over here.

138
00:08:35,100 --> 00:08:38,730
We have one E over here and we have one E over here.

139
00:08:38,730 --> 00:08:44,760
So in a way the tasks with the highest frequency are becoming one unit.

140
00:08:44,760 --> 00:08:51,210
So we can consider that we are putting one unit over here, another unit over here and another unit

141
00:08:51,210 --> 00:08:51,900
over here.

142
00:08:51,900 --> 00:08:52,440
Okay.

143
00:08:52,440 --> 00:08:58,020
And then let's see how we can proceed with these four steps that we had previously discussed.

144
00:08:58,020 --> 00:09:02,670
So the first step is to identify the number of parts that are there.

145
00:09:02,670 --> 00:09:10,350
And you can see that even in this example the number of parts is just the highest frequency minus one

146
00:09:10,350 --> 00:09:13,560
which is three minus one which is equal to two.

147
00:09:13,740 --> 00:09:20,430
The second step is to identify the number of slots that we have in these parts.

148
00:09:20,430 --> 00:09:20,880
Okay.

149
00:09:20,880 --> 00:09:29,550
And for that we just need to multiply the number of parts which is two with n minus the number of tasks

150
00:09:29,550 --> 00:09:31,650
with the highest frequency minus one.

151
00:09:31,650 --> 00:09:33,390
So this is a tweak okay.

152
00:09:33,900 --> 00:09:38,880
Again multiplying this over here with the number of parts is pretty straightforward.

153
00:09:38,880 --> 00:09:42,540
Because whatever we have over here we have that over here as well.

154
00:09:42,540 --> 00:09:44,910
So this part is pretty straightforward.

155
00:09:44,910 --> 00:09:46,560
But what about this over here.

156
00:09:46,560 --> 00:09:49,590
Notice that from N which is three.

157
00:09:49,590 --> 00:09:57,390
In this case we are subtracting one which is the number of tasks with highest frequency minus one.

158
00:09:57,390 --> 00:10:01,560
So in this case we have two tasks which have the highest frequency.

159
00:10:01,560 --> 00:10:04,620
And from this we are subtracting one to get one.

160
00:10:04,620 --> 00:10:08,760
Now let's say we had one more task over here which is f f f.

161
00:10:08,760 --> 00:10:12,600
We would place f over here, over here and over here.

162
00:10:12,600 --> 00:10:17,220
And in this case this two would be three and three minus one would be two.

163
00:10:17,220 --> 00:10:22,110
And when you do n minus two that would be three minus two which is equal to one.

164
00:10:22,110 --> 00:10:26,730
And notice that's what is left in this section or in this part.

165
00:10:26,730 --> 00:10:35,970
So that's why the number of slots in each part which is left is equal to n minus the number of tasks

166
00:10:35,970 --> 00:10:38,220
with the highest frequency minus one.

167
00:10:38,220 --> 00:10:40,380
In this case that's equal to two.

168
00:10:40,380 --> 00:10:46,260
And then to identify the total number of slots which are available, we just multiply this two over

169
00:10:46,260 --> 00:10:50,790
here with the number of parts that we have, which in this case is two itself.

170
00:10:50,790 --> 00:10:57,300
So the number of slots which is available over here is two into two which is equal to four.

171
00:10:57,300 --> 00:10:57,990
All right.

172
00:10:57,990 --> 00:11:04,350
So that brings us to step number three which is to identify the number of remaining tasks.

173
00:11:04,350 --> 00:11:11,970
And for this we just need to identify how many tasks are already filled which are the tasks which have

174
00:11:11,970 --> 00:11:13,440
the highest frequency.

175
00:11:13,440 --> 00:11:13,830
Okay.

176
00:11:13,830 --> 00:11:17,490
So in this case we can see that the highest frequency is three.

177
00:11:17,490 --> 00:11:19,410
And there are two such tasks.

178
00:11:19,410 --> 00:11:23,670
So we have already filled three into two which is six tasks.

179
00:11:23,670 --> 00:11:29,820
And the remaining tasks would be the total length of the tasks array minus six okay.

180
00:11:29,820 --> 00:11:34,650
Which is in this case seven minus six which is equal to one.

181
00:11:34,650 --> 00:11:41,580
And that brings us to the next step, which is to identify the number of empty slots that would remain.

182
00:11:41,580 --> 00:11:42,210
So.

183
00:11:42,210 --> 00:11:46,350
So far we have seen that there is just one task to be filled.

184
00:11:46,350 --> 00:11:51,210
And we have also seen that we have four slots remaining.

185
00:11:51,210 --> 00:11:51,600
Okay.

186
00:11:51,600 --> 00:11:58,620
So the number of empty slots in this case would be four minus one which is equal to three.

187
00:11:58,620 --> 00:12:00,600
So we'll have three empty slots.

188
00:12:00,600 --> 00:12:06,960
And once we get this three the answer would be the length of the input tasks array, which in this case

189
00:12:06,960 --> 00:12:11,940
is seven plus the number of idle or empty tasks which is equal to three.

190
00:12:11,940 --> 00:12:16,320
So the answer would be seven plus three which is equal to ten.

191
00:12:16,320 --> 00:12:18,000
And we can just return this.

192
00:12:18,000 --> 00:12:20,310
So this is how we can solve this question.

193
00:12:20,310 --> 00:12:24,480
And again notice it involves these four steps okay.

194
00:12:24,480 --> 00:12:30,330
Whether it's having one task with the highest frequency or whether there are multiple tasks with the

195
00:12:30,330 --> 00:12:35,280
highest frequency, we just need to follow these four steps to solve this question.

196
00:12:35,340 --> 00:12:37,530
So to summarize remember.

197
00:12:37,650 --> 00:12:44,220
To solve this question, we just need to do number of tasks plus number of empty slots in the best arrangement.

198
00:12:44,220 --> 00:12:49,860
And we have discussed two examples to understand the approach we can take to solve this question.

199
00:12:49,860 --> 00:12:51,630
And these were the examples.

200
00:12:51,630 --> 00:12:56,850
So in this example there is just one task which has the highest frequency which is three.

201
00:12:56,850 --> 00:13:00,840
And in this example there are two such tasks okay.

202
00:13:00,840 --> 00:13:06,840
And there were four steps over here in the approach that we have discussed, which is to first identify

203
00:13:06,840 --> 00:13:11,730
the number of parts and after that to identify the slots in the parts.

204
00:13:11,730 --> 00:13:17,190
And then we would have to identify the remaining tasks to be placed in the slots.

205
00:13:17,190 --> 00:13:23,040
And finally using this we would identify the number of empty or idle slots.

206
00:13:23,040 --> 00:13:28,800
And once we have identified this, we can just solve the question by returning the length of the tasks

207
00:13:28,800 --> 00:13:32,640
array plus the number of idle or empty slots.

208
00:13:32,670 --> 00:13:36,540
Okay, now quickly going through these examples over here.

209
00:13:36,540 --> 00:13:39,510
This is the highest frequency item which is a.

210
00:13:39,510 --> 00:13:44,760
And over here we have two items or two tasks which have the highest frequency.

211
00:13:44,760 --> 00:13:50,250
So in this case the number of items with the highest frequency is equal to two.

212
00:13:50,280 --> 00:13:50,760
Okay.

213
00:13:50,760 --> 00:13:56,550
Now to identify the number of parts as we have discussed, all that we need to do is we need to do highest

214
00:13:56,550 --> 00:14:01,410
frequency minus one, which in both of the cases is equal to two.

215
00:14:01,440 --> 00:14:08,340
Now to identify the slots in the parts, what we have to do over here was we had to multiply the number

216
00:14:08,340 --> 00:14:12,660
of parts with n okay n is another input parameter for the question.

217
00:14:12,660 --> 00:14:14,670
Let's say n is equal to two.

218
00:14:14,700 --> 00:14:16,200
That could be the case okay.

219
00:14:16,200 --> 00:14:23,130
So to identify the number of slots in the parts over here, we've seen that we can just do p into n.

220
00:14:23,130 --> 00:14:31,800
But if there are more than one item with the highest frequency then this would be p into n minus the

221
00:14:31,800 --> 00:14:34,650
number of items with the highest frequency minus one.

222
00:14:34,650 --> 00:14:36,750
Okay, so that would be two minus one.

223
00:14:36,750 --> 00:14:42,600
In this example, notice that if there is just one item with the highest frequency, this would be one

224
00:14:42,600 --> 00:14:44,820
minus one and it would cancel out.

225
00:14:44,820 --> 00:14:48,240
And this over here would just become p into n.

226
00:14:48,240 --> 00:14:48,810
All right.

227
00:14:48,810 --> 00:14:56,040
And in the next step we would just try to identify how many tasks are remaining to be filled in the

228
00:14:56,040 --> 00:15:01,290
slots, which are in fact the tasks which don't have the highest frequency.

229
00:15:01,290 --> 00:15:07,560
And for that we just need to subtract the number of highest frequency items from the total number of

230
00:15:07,560 --> 00:15:08,490
tasks given.

231
00:15:08,490 --> 00:15:15,060
So in this case that would be five minus three, and in this case that would be seven minus three into

232
00:15:15,060 --> 00:15:15,990
two okay.

233
00:15:15,990 --> 00:15:17,460
So that's pretty straightforward.

234
00:15:17,460 --> 00:15:24,360
And once we have the number of remaining tasks to be filled we can identify the idle slots by doing

235
00:15:24,360 --> 00:15:25,680
s minus t.

236
00:15:25,680 --> 00:15:26,220
Okay.

237
00:15:26,220 --> 00:15:31,950
So these are the steps that we have discussed in the examples which can be used to solve this question.

238
00:15:31,950 --> 00:15:38,010
Now one more thing that you need to keep in mind is that the number of idle tasks should never be less

239
00:15:38,010 --> 00:15:38,670
than zero.

240
00:15:38,670 --> 00:15:45,450
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

241
00:15:45,450 --> 00:15:48,120
is the input array and n is equal to one okay.

242
00:15:48,120 --> 00:15:51,420
So you'd have to fill a, leave a space and fill a.

243
00:15:51,420 --> 00:15:54,570
And then when it comes to B's you'd have to fill B over here.

244
00:15:54,570 --> 00:15:56,130
And you can fill B over here.

245
00:15:56,130 --> 00:16:00,810
And then when we take a look at the remaining tasks it would be these two.

246
00:16:00,810 --> 00:16:03,120
But the slots are zero right.

247
00:16:03,120 --> 00:16:05,430
So zero minus two would give you minus two.

248
00:16:05,430 --> 00:16:10,620
But in that case you have to just take the number of slots which are idle as zero.

249
00:16:10,620 --> 00:16:15,990
And in that case, notice that the best way of filling the tasks is putting C and D over here.

250
00:16:15,990 --> 00:16:22,830
And in this case, the total number of intervals required is in fact the length of the tasks array itself.

251
00:16:22,830 --> 00:16:28,890
So again, a quick side note over here, the number of empty or idle slots should never be less than

252
00:16:28,890 --> 00:16:29,310
zero.

253
00:16:29,310 --> 00:16:32,730
So if it goes less than zero you can just take it as zero.

254
00:16:32,730 --> 00:16:39,630
So in other words we'll just take the maximum between zero and s minus t okay.

255
00:16:39,630 --> 00:16:43,710
And we'll see this again when we discuss how we can code this solution.