Buckle practice - 17 task scheduler

17 Task scheduler

1. Problem description
Given an array of characters CPU List of tasks to be performed . It contains... In uppercase A - Z Letters indicate 26 There are different kinds of tasks . Tasks can be performed in any order , And every task can be in 1 In unit time .CPU You can perform a task in any unit of time , Or on standby .

However , There must be a length of n The cooling time of , So at least there's continuity n In units of time CPU On different missions , Or on standby .

You need to calculate the minimum time required to complete all tasks .

Example ：

Input ：tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 2

Output ：8

explain ：A -> B -> ( On standby ) -> A -> B -> ( On standby ) -> A -> B.

  In this example , The interval length between two tasks of the same type must be  n = 2  The cooling time of , It takes only one unit time to perform a task , So in the middle （ On standby ） state . 

explain ：

The total number of tasks is [1, 10000].

n The value range of is [0, 100].

Refer to the following main function ：

int main()

{

vector<char> v;

int len,n;

char data;

cin>>len;

for(int i=0; i<len; i++)

{

    cin>>data;

    v.push_back(data);

}

cin>>n;

int result=Solution().leastInterval(v,n);

cout<<result<<endl;

return 0;

}

2. Enter description
First enter the number of tasks len

Then input len A capital A - Z Letter , No spaces 、 No quotes

Last input n
3. The output shows that
Output an integer , Show the result
4. Example
Input
6
AAABBB
2
Output
8
5. Code

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

bool compare(int x, int y)
{
    
	return x > y ;
}


int leastInterval(vector<char>tasks, int n)
{
      // thought ： Bucket thought , Set the size to  n+1  My bucket , The task with the largest number of tasks 
	// Reference resources https://leetcode.cn/problems/task-scheduler/solution/tong-zi-by-popopop/
	//1. Sort the number of occurrences of all tasks 
	//int len = tasks.size();// Get the total number of tasks 
	vector<int>vec(26);// Used to record the number of occurrences of each task 
	for (int i = 0; i < tasks.size(); i++)
	{
    
		vec[tasks[i] - 'A']++; // Skillfully count the number of times each character appears 
	}
	
	sort(vec.begin(), vec.end(), compare);// Pay attention to this side compare Function writing , Use bool Return to comparison  , Here is the descending order 

	//2. Count the tasks of the last bucket x
	int cnt = 1;// Used to calculate the number of tasks of the last bucket x
	while (cnt < vec.size()&& vec[cnt] == vec[0])// Be careful not to fall into a dead circle ,vec[cnt]==vec[0] Must be in while（） in , Otherwise, there will be a dead cycle //while (cnt < vec.size())
	{
                                                                                                                        //{ if(vec[cnt]==vec[0]) cnt++;}
                                               
	   //vec[0] Stored is the maximum number of tasks in all tasks N, After calculation vec[1],vec[2]etc Number of tasks and vec[0] Equal number , Calculation x
			cnt++;
	}
	int x = cnt;
	int N = vec[0];
	//3. Compare NUM1 and NUM2 size ,NUM1=（N-1）*（n+1）+x; NUM2=tasks.size();  Return the largest 
	int NUM1 = (N - 1)*(n + 1) + x;
	int NUM2 = tasks.size();
	return max(NUM1, NUM2);
}
int main()

{
    

	vector<char> v;

	int len, n;

	char data;

	cin >> len;

	for (int i = 0; i < len; i++)

	{
    

		cin >> data;

		v.push_back(data);

	}

	cin >> n;

	int result = leastInterval(v, n);

	cout << result << endl;

	return 0;

}