Task Scheduler

Posted: 6 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1

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’.
Try Problem