Solution
Explanation by jinzhou: The key is to find out how many idles do we need. Let’s first look at how to arrange them. it’s not hard to figure out that we can do a “greedy arrangement”: always arrange task with most frequency first. E.g. we have following tasks : 3 A, 2 B, 1 C. and we have n = 2. According to what we have above, we should first arrange A, and then B and C. Imagine there are “slots” and we need to arrange tasks by putting them into “slots”. Then A should be put into slot 0, 3, 6 since we need to have at least n = 2 other tasks between two A. After A put into slots, it looks like this:
A ? ? A ? ? A “?” is “empty” slots.
Now we can use the same way to arrange B and C. The finished schedule should look like this:
A B C A B # A “#” is idle
Now we have a way to arrange tasks. But the problem only asks for number of CPU intervals, so we don’t need actually arrange them. Instead we only need to get the total idles we need and the answer to problem is just number of idles + number of tasks.
To get the number of idles, we will employ a greedy approach by placing the character which is most frequent first. Let’s take a different example: [A, A, A, A, B, B, C, D, E] and n = 2.
We will first arrange A:
A ? ? A ? ? A ? ? A
This leaves us with 6 empty slots = (count(A)-1)*n
Now, we fill B:
A B ? A B ? A ? ? A
This leaves us with 4 empty slots = previous count - count(B)
Fill C, D, E:
A B C A B D A E ? A
Empty slots = 1 = previous count - [count(C) + count(D) + count(E)]
We can devise an algorithm using this approach. Note that we just need the counts, not the alphabet associated with it. Also, we only need to count for empty slots as long as the count is greater than 0. Suppose n = 1 and array is [A, A, B, C, D, E, F] We fill A, B, C like this: A B A C Now, when filling rest of them, we don’t have to worry about empty slots anymore! So our answer would simply be the size of array.
There can be one edge case though: Consider [A, A, A, B, B, B] and n = 2 Filling A:
A ? ? A ? ? A
Empty count = 4
Now, when we fill B:
A B ? A B ? A B
Empty count = 2 which is not equal to previous count - count(B)! This is because the last B is placed in the last region where we don’t have any empty slots. This edge case arises when we have count(B) = count(A). To deal with this, we can simply update our algorithm: empty slot count = previous count - min(maxFreq-1, count(B)); where maxFreq is the maximum frequency in the input array (count(A) in this case).
Code:
int leastInterval(vector<char>& tasks, int n) {
vector<int> v(26, 0);
int totCount = tasks.size();
for (int i=0; i<totCount; i++)
v[tasks[i]-'A']++;
priority_queue<int> pq;
// we only need to store the counts in priority queue
for (int i=0; i<v.size(); i++)
if (v[i])
pq.push(v[i]);
// get the empty slots by placing the element with highest frequency
int idleCount = (pq.top()-1)*n;
int maxFreq = pq.top();
pq.pop();
// as long as all elements are not placed and empty slot count > 0
while (!pq.empty() && idleCount > 0) {
idleCount -= min(maxFreq-1, pq.top());
pq.pop();
}
// if empty slot count is less than or equal to 0, we can place all elements without using any empty slot
if (idleCount<=0)
return totCount;
else
return totCount+idleCount;
}