Problem Statement:
You are given an array of CPU tasks and a cool off period between the same task “n”.
You need to re-arrange the tasks such that, the time run should be minimum.
Example
Input: tasks = [“A”,”A”,”B”,”B”,”B”], n = 2
Output: 8
Explanation:
A -> B -> idle -> A -> B -> idle -> B
According to the question, there should be atleast 2 unit between the same task.
So task A and task B can run simultaneously.
Solution
We can solve this problem with the help of greedy method.
1. First count the frequency of most occurring character in the string.
2. Then, the maximum time taken according to the cooling period n will be result = (max_freq_char -1) * (n +1);
Example:
Tasks = [“A”,”A”,”A”,”A”,”B”,”B”,”B”], n = 2
A _ _ A _ _ A_ _ A
3. Once we know the maximum number of idle spaces, we need to reduce the space every-time we find a task that will fill up that idle space.
Solution in C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int least_interval(vector<char >& tasks, int n)
{
vector<int> count(26, 0);
int tasks_size = tasks.size();
int max_freq = 0;
for (auto &it : tasks) {
count[it - 65]++;
max_freq = max(max_freq, count[it - 65]);
}
int result = (max_freq - 1) * (n+1);
for (auto &it : count) {
if (max_freq == it) {
result++;
}
}
return max(result, tasks_size);
}
int main()
{
vector<char> tasks = {'A','A','A','B','B','B'};
int n = 2;
cout << "The min interval required are " <<least_interval(tasks, n)
<< endl;
return 0;
}
Output:
The min interval required are 8