1
00:00:00,430 --> 00:00:01,600
Welcome back.

2
00:00:01,600 --> 00:00:07,600
In the previous video, we have discussed the approach that we can take to solve this question in detail.

3
00:00:07,600 --> 00:00:08,410
Over here.

4
00:00:08,410 --> 00:00:12,490
Let's quickly write the pseudocode for the approach that we came up with.

5
00:00:12,490 --> 00:00:16,510
And then we will go ahead and implement the code of this as well.

6
00:00:16,510 --> 00:00:22,270
So as we discussed in the previous video, the first thing that we need to do to solve this question

7
00:00:22,270 --> 00:00:30,280
is to traverse through the tasks which are given to us and identify the frequency for each task in the

8
00:00:30,280 --> 00:00:31,750
input tasks array.

9
00:00:31,750 --> 00:00:32,290
Okay.

10
00:00:32,290 --> 00:00:38,620
And after we have identified this, there are just 4 or 5 steps to solve this question.

11
00:00:38,620 --> 00:00:45,280
First, we'll go ahead and try to identify the number of parts that would be there.

12
00:00:45,280 --> 00:00:53,200
Once we have organized or arranged the task that occurs at the highest frequency, ensuring that these

13
00:00:53,200 --> 00:00:56,290
tasks are separated by n intervals.

14
00:00:56,290 --> 00:00:59,560
And again, remember n is one of the inputs in the question.

15
00:00:59,560 --> 00:00:59,950
Okay.

16
00:00:59,950 --> 00:01:06,010
So this would be the first thing that we do after we have identified the frequencies of the tasks which

17
00:01:06,010 --> 00:01:06,910
are given to us.

18
00:01:06,910 --> 00:01:13,600
And if we say that this is equal to P, we have seen that we can identify p or the number of parts by

19
00:01:13,600 --> 00:01:17,350
just doing the highest frequency minus one.

20
00:01:17,350 --> 00:01:22,450
So again this means that let's say the input array has these elements okay.

21
00:01:22,450 --> 00:01:26,620
So in this case we can see that the highest frequency is three.

22
00:01:26,620 --> 00:01:30,550
And there would be in this case two parts which is three minus one.

23
00:01:30,550 --> 00:01:33,550
And the reason for this is we would arrange C over here.

24
00:01:33,550 --> 00:01:38,080
Then we'll just have n intervals and then again c and n intervals.

25
00:01:38,080 --> 00:01:39,460
And then again c.

26
00:01:39,460 --> 00:01:43,420
And notice because we had three c's we are left with two parts.

27
00:01:43,420 --> 00:01:48,400
So parts or p is equal to the highest frequency minus one.

28
00:01:48,400 --> 00:01:54,520
Now once we have done this we can go ahead and identify the number of slots in the parts.

29
00:01:54,520 --> 00:02:01,450
And for that we need to multiply the parts with the number of slots in each part, which would be n

30
00:02:01,450 --> 00:02:10,030
minus the max count, minus one, where max count is the number of tasks that are there that have the

31
00:02:10,030 --> 00:02:11,200
highest frequency.

32
00:02:11,200 --> 00:02:11,740
Okay.

33
00:02:11,920 --> 00:02:16,840
Now again, this means that let's say the input tasks array is something like this.

34
00:02:16,840 --> 00:02:25,150
Now in this case max count would be two because we have C and A which each occur three times which is

35
00:02:25,150 --> 00:02:26,830
the highest frequency okay.

36
00:02:26,830 --> 00:02:32,740
So again the slots in parts would be p into n minus max count minus one.

37
00:02:32,740 --> 00:02:39,820
And after this we can go ahead and identify the remaining tasks which we would have to fill in these

38
00:02:39,820 --> 00:02:40,360
slots.

39
00:02:40,360 --> 00:02:43,060
Or at least try to fill in these slots.

40
00:02:43,060 --> 00:02:51,700
And to identify this, we can just do the length of tasks minus the highest frequency into max count,

41
00:02:51,700 --> 00:02:56,710
because we would have arranged already the tasks which have the highest frequency.

42
00:02:56,710 --> 00:03:03,550
For example, in this example we would have already arranged C and a, and we would just be left with

43
00:03:03,550 --> 00:03:05,740
tasks which don't have this frequency.

44
00:03:05,740 --> 00:03:09,100
Like for example if the input array were something like this.

45
00:03:09,100 --> 00:03:16,000
So notice over here we have b, c and d which don't have a frequency of three which is the highest frequency

46
00:03:16,000 --> 00:03:17,080
in this example.

47
00:03:17,080 --> 00:03:24,040
And therefore we just need to identify this four and for that we can just subtract from the length of

48
00:03:24,040 --> 00:03:26,890
tasks which would be the total number of tasks.

49
00:03:26,890 --> 00:03:32,890
The number of times the task with the highest frequency occurs, which in this case is six.

50
00:03:32,890 --> 00:03:39,160
And to get six over here we can just multiply the highest frequency, which is three by the max count

51
00:03:39,160 --> 00:03:39,970
which is two.

52
00:03:39,970 --> 00:03:40,360
Okay.

53
00:03:40,360 --> 00:03:47,170
So that gives us t which is the remaining number of tasks which we will try to place in the slots.

54
00:03:47,170 --> 00:03:47,590
Okay.

55
00:03:47,590 --> 00:03:49,060
These slots over here.

56
00:03:49,180 --> 00:03:56,980
And once we have identified this we can identify the number of empty slots which would be s minus t.

57
00:03:56,980 --> 00:03:57,340
Okay.

58
00:03:57,340 --> 00:03:59,320
Now there is a caveat to this.

59
00:03:59,320 --> 00:04:04,330
Now if s minus t is less than zero then we will just take zero okay.

60
00:04:04,330 --> 00:04:05,950
Now this is possible.

61
00:04:05,950 --> 00:04:08,140
Like I've explained earlier as well.

62
00:04:08,140 --> 00:04:15,010
Let's say the input array is a, a, b, b, c, d and let's say n is equal to one.

63
00:04:15,010 --> 00:04:15,400
Okay.

64
00:04:15,400 --> 00:04:20,530
Now in this case we would place a over here, leave one space and then place a.

65
00:04:20,530 --> 00:04:23,140
So we have placed these two tasks.

66
00:04:23,140 --> 00:04:26,620
And then we would go ahead and place these two tasks as well.

67
00:04:26,620 --> 00:04:31,030
Because they have the same frequency which is the highest frequency which is equal to two.

68
00:04:31,060 --> 00:04:35,110
So we would go ahead and place a b over here and B over here.

69
00:04:35,110 --> 00:04:40,630
Now notice that in this case s is equal to zero because we don't have anything over here.

70
00:04:40,630 --> 00:04:42,790
And t is equal to two right.

71
00:04:42,790 --> 00:04:46,030
And zero minus two gives us minus two.

72
00:04:46,030 --> 00:04:52,480
But then in that case we would take e as just zero because we can just place C and D over here.

73
00:04:52,480 --> 00:04:58,180
And with this arrangement notice that there are in fact no idle or empty slots.

74
00:04:58,180 --> 00:04:59,470
That's why we would just take.

75
00:04:59,840 --> 00:05:03,260
Slots or idols as zero in this case.

76
00:05:03,260 --> 00:05:04,730
Okay, so that's it.

77
00:05:04,730 --> 00:05:12,110
Now once we have identified the number of idols or empty slots, we can just return the answer which

78
00:05:12,110 --> 00:05:14,900
would be E plus the length of tasks.

79
00:05:14,900 --> 00:05:18,020
So this is the pseudo code for solving this question.