Last Updated: 6 Jan, 2021
Task Scheduler
Moderate
Asked in companies
A ninja needs to complete ‘n’ tasks. Each task is represented by an uppercase letter of the English alphabet. Different letters are assigned to different tasks. A ninja can complete tasks in any order. He takes one unit of time to complete one task. For each unit of time, he could complete either one task or just be idle.
Ninja easily gets bored by doing the same task again. So he decided to keep at least ‘t’ units of time between any two same tasks.
You are given a string ‘tasks’ consisting of ‘n’ uppercase letters of the English alphabet, representing the tasks ninja need to complete, and an integer ‘t’ representing the least units of time between any two same tasks. Find out the minimum total units of time ninja will take to complete all ‘n’ tasks.
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains two space-separated integers ‘n’ and ‘t’; representing the number of tasks and the least units of time between any two same tasks respectively.
The second line of the test case contains a string ‘tasks’ consisting of the ‘n’ uppercase character of the English alphabet.
Output Format :
For each test case, print the minimum total units of time ninja will take to complete all ‘n’ tasks.
Print the output of each test case in a new line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
1 <= n <= 10^4
1 <= t <= 100
Where ‘T’ is the number of test cases and ‘n’ is the number of tasks and ‘t’ is the least units of time between any two same tasks.
Time Limit : 1 sec
Approaches
The idea is to add all the tasks in the Priority Queue with their frequency (number of occurrences), higher is frequency higher should be its priority. In each round Ninja picks ‘t+1’ tasks with the highest frequency and completes them, if there is less than ‘t+1’ task, then ninja needs to be idle for the remaining time.
- Create an integer array ‘freq’ of size 26. It will keep the frequency (number of occurrences) of each character/task in the string ‘tasks’ where ‘freq[i]’ gives the frequency of ‘ith’ character of the uppercase English alphabet.
- Iterate over the string ‘tasks’ and for each character ‘ch’ increment freq[ch-’A’] by 1.
- Create a Priority Queue and add all tasks with their frequency. Tasks with higher frequency should have higher priority.
- Initialize an integer variable ‘leastTime’:= 0.
- Run a while loop till the priority queue is not empty and in each iteration do the following.
- Create an empty vector ‘temp’.
- Run a loop where ‘i’ ranges from 0 to ‘t’ and in each iteration pop the top (Highest priority) task from the priority queue then decrease its frequency by 1 and add this task to the vector ‘temp’. If the priority queue becomes empty then break the loop.
- Iterate over the vector ‘temp’ and add all the tasks in the priority queue, whose frequency is greater than 0.
- If the priority queue is not empty then increment ‘leastTime’ by ‘t+1’ otherwise increment ‘leastTime’ by the size of the vector ‘temp’.
- Return ‘leastTime’.
Let's suppose the maximum frequency (number of occurrences) of the task/character in string ‘tasks’ is ‘maxFreq’ and the number of tasks with that maximum frequency is ‘countMaxFreq’. We have ‘n’ tasks and a ninja wants at least ‘t’ unit of time between any two same tasks.
Now, we can make a ‘maxFreq-1’ group of the size ‘t’+1 ( the last group will not contain idle spaces, it will contain the tasks with maximum frequency only). Each group has a different task with maximum frequency and the remaining number of empty slots i.e ‘_’ (if there is less than ‘t’+1 such task). The total length of these ‘maxFreq’ groups will be (‘maxFreq’-1)*(t+1) + ‘countMaxFreq’. Here, ‘countMaxFreq’ tells the size of the last group. Note, the units of time required is equal to the total length of these ‘maxFreq’ groups.
For example, Let there be two tasks ‘A’ and ‘B’ having maximum frequency 3. And ‘t’ = 2.
Then, we can arrange these tasks in order AB_AB_AB, where _ represent the time when a ninja is idle. Since the maximum frequency of a task (in this case ‘A’ and ‘B’) is 3, there will be 3 groups. The size of the first two groups will be equal to ‘t’+1, which is 3 ( denoting (AB_)(AB_)). The last group won’t contain the idle spaces and will only contain the characters left which are the characters with maximum frequency, AB in this case, which gives size 2. So,it takes takes at least (3-1)*(2+1) + 2 = 8 units of time.
After placing at most ‘t’+1. tasks with the highest frequency, we can place all the remaining tasks in empty slots (the time when a ninja is idle), If all the empty slots get filled then we can increase the size of groups. Thus answer will be maximum of ‘n’ and (‘maxFreq’-1)*(t+1) + ‘countMaxFreq’. The answer will be ‘n’ when all empty slots get filled
The implementation can be done as follow -:
- Create an integer array ‘freq’ of size 26. It will keep the frequency (number of occurrences) of each character/task in the string ‘tasks’ where ‘freq[i]’ gives the frequency of ‘ith’ character of the uppercase English alphabet.
- Initialize an integer variable ‘maxFreq’:= 0 that represents the maximum frequency of the task/character in string ‘tasks’.
- Initialize another integer variable ‘countMaxFreq’:=0 that represents the number of tasks/characters having a frequency equal to the maximum frequency.
- Iterate over all character of string tasks and do following -:
- Increment frequency of current character by 1 in ‘freq’ array.
- If the frequency of this character becomes greater than ‘maxFreq’ then assign its frequency to ‘maxFreq’, and replace the value of ‘countMaxFreq’ by 1 because till now there is only 1 character with that maximum frequency.
- Otherwise, if the frequency of this character becomes equal to ‘maxFreq’ then increment ‘countMaxFreq’ by 1.
- The minimum total units of time ninja required will be the maximum of ‘n’ and (‘maxFreq’-1)*(t+1) + ‘countMaxFreq’ as discussed above. You should return this value.