Task Scheduler
Task Scheduler:
Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.
However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.
Return the least number of units of times that the CPU will take to finish all the given tasks.
Example 1:
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation:
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.
Example 2:
Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.
Example 3:
Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation:
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A
Constraints:
1 <= task.length <= 10^4tasks[i]is upper-case English letter.- The integer
nis in the range[0, 100].
Try this Problem on your own or check similar problems:
Solution:
- Java
- JavaScript
- Python
- C++
public int leastInterval(char[] tasks, int n) {
int[] map = new int[26];
int freqOfMostOcurringTask = 0;
int countOfMostOccuringTasks = 0;
for(char task : tasks) {
++map[task - 'A'];
if(freqOfMostOcurringTask == map[task - 'A']) {
++countOfMostOccuringTasks;
}
else if(freqOfMostOcurringTask < map[task - 'A']) {
freqOfMostOcurringTask = map[task - 'A'];
countOfMostOccuringTasks = 1;
}
}
int numberOfGaps = freqOfMostOcurringTask - 1;
int gapLength = n - (countOfMostOccuringTasks - 1);
int totalLengthofGaps = numberOfGaps * gapLength;
int remainingTasks = tasks.length - freqOfMostOcurringTask * countOfMostOccuringTasks;
int idles = Math.max(0, totalLengthofGaps - remainingTasks);
return tasks.length + idles;
}
/**
* @param {character[]} tasks
* @param {number} n
* @return {number}
*/
var leastInterval = function (tasks, n) {
const map = new Array(26).fill(0);
let freqOfMostOccurringTask = 0;
let countOfMostOccurringTasks = 0;
for (const task of tasks) {
const index = task.charCodeAt() - "A".charCodeAt();
map[index]++;
if (freqOfMostOccurringTask === map[index]) {
countOfMostOccurringTasks++;
} else if (freqOfMostOccurringTask < map[index]) {
freqOfMostOccurringTask = map[index];
countOfMostOccurringTasks = 1;
}
}
const numberOfGaps = freqOfMostOccurringTask - 1;
const gapLength = n - (countOfMostOccurringTasks - 1);
const totalLengthOfGaps = numberOfGaps * gapLength;
const remainingTasks =
tasks.length - freqOfMostOccurringTask * countOfMostOccurringTasks;
const idles = Math.max(0, totalLengthOfGaps - remainingTasks);
return tasks.length + idles;
};
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
map = [0] * 26
freqOfMostOccurringTask = 0
countOfMostOccurringTasks = 0
for task in tasks:
index = ord(task) - ord('A')
map[index] += 1
if freqOfMostOccurringTask == map[index]:
countOfMostOccurringTasks += 1
elif freqOfMostOccurringTask < map[index]:
freqOfMostOccurringTask = map[index]
countOfMostOccurringTasks = 1
numberOfGaps = freqOfMostOccurringTask - 1
gapLength = n - (countOfMostOccurringTasks - 1)
totalLengthOfGaps = numberOfGaps * gapLength
remainingTasks = len(tasks) - freqOfMostOccurringTask * countOfMostOccurringTasks
idles = max(0, totalLengthOfGaps - remainingTasks)
return len(tasks) + idles
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
vector<int> map(26, 0);
int freqOfMostOccurringTask = 0;
int countOfMostOccurringTasks = 0;
for (char task : tasks) {
int index = task - 'A';
map[index]++;
if (freqOfMostOccurringTask == map[index]) {
countOfMostOccurringTasks++;
} else if (freqOfMostOccurringTask < map[index]) {
freqOfMostOccurringTask = map[index];
countOfMostOccurringTasks = 1;
}
}
int numberOfGaps = freqOfMostOccurringTask - 1;
int gapLength = n - (countOfMostOccurringTasks - 1);
int totalLengthOfGaps = numberOfGaps * gapLength;
int remainingTasks = tasks.size() - freqOfMostOccurringTask * countOfMostOccurringTasks;
int idles = max(0, totalLengthOfGaps - remainingTasks);
return tasks.size() + idles;
}
};
Time/Space Complexity:
- Time Complexity: O(n)
- Space Complexity: O(1)
Explanation:
If you look at example it will become obvious that the best task scheduling is the greedy one, in other words arranging the most frequent tasks first and then filling the gaps with remaining tasks. To count the frequency of tasks since tasks are only upper-case English letter, we only need to create array of 26 letters to keep the count. We iterate over the tasks and count their frequency each time checking if have a new most frequent task or if the current task has the same frequency as the most frequent task (which also makes it the most frequent task). Then to calculate the number of idles (spaces we cannot fill with tasks) we do the following:
- If you have 3 occurrences of most frequent task, you need 2 gaps between those 3 occurrences (e.g.
A gap A gap A). - To calculate the gap length, we place all of tasks with highest frequency
countOfMostOccuringTasks(we subtract one since that's our A from the previous example), and what we are left is the number of spaces we have to fill to haventasks in between. totalLengthofGapswill just be the length of one gapgapLengthmultiplied with total number of gapsnumberOfGaps.- To get number of remaining task (tasks with lower frequency than the ones with highest occurrence frequency) we just subtract number of tasks with highest frequency from the total number of tasks.
- To get number of idles (spaces we cannot fill with tasks) we subtract the
remainingTasksfrom thetotalLengthofGaps. - Finally, we add the number of idles to the total number of tasks (each task will execute) and return it as our final result.