博客

题目：给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A – Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。你需要计算完成所有任务所需要的最短时间。

示例 1：输入: tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 2

输出: 8

执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.

（百度测试开发岗二面的一个面试题）

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int calculateMaxTime(string task, int n)
{
    int len = task.size();
    if(len <= 0)return 0;
    vector<char> vc(26, 0);
    //统计每个类型出现次数
    for(int i = 0; i < len; i++)
    {
        vc[task[i] - 'A']++;
    }
	sort(vc.begin(), vc.end());//对次数进行排序
    int val = vc[25];
    int maxtime = 0;
	int count = 0;
	for(int i = 25; i >= 0; i--)
	{
		if(vc[i] == val)count++;//一共可以分为val组，count是最后一组的个数
	}
	maxtime = (val - 1)*(n+1) + count;
    return maxtime;
}
int main()
{
    string task = "AAAAABBBC";
    int n = 2;
    int max = calculateMaxTime(task, n);
    cout<<max<<endl;
    return 0;
}