Greedy: Schedule task efficiently

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

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *