题目描述

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。

然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

解题思路

所以整体的解题步骤如下：

计算每个任务出现的次数
找出出现次数最多的任务，假设出现次数为 x
计算至少需要的时间 (x - 1) * (n + 1)，记为 min_time
计算出现次数为 x 的任务总数 count，计算最终结果为 min_time + count

code [python]

class Solution(object):
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int
        """
        length = len(tasks)
        if length <= 1:
            return length
        
        # 用于记录每个任务出现的次数
        task_map = dict()
        for task in tasks:
            task_map[task] = task_map.get(task, 0) + 1
        # 按任务出现的次数从大到小排序
        task_sort = sorted(task_map.items(), key=lambda x: x[1], reverse=True)
        
        # 出现最多次任务的次数
        max_task_count = task_sort[0][1]
        # 至少需要的最短时间
        res = (max_task_count - 1) * (n + 1)
        
        for sort in task_sort:
            if sort[1] == max_task_count:
                res += 1
        
        # 如果结果比任务数量少，则返回总任务数
        return res if res >= length else length

C++ code

//任务调度
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<unordered_map>
using namespace std;
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
       //获取每个记录中任务出现的次数
        int time_count = 0;
        unordered_map<char,int> hash;
        for(auto a:tasks){
            hash[a]++;
        }
        priority_queue<int>queue1, queue2;
        for (auto a : hash) {
            queue1.push(a.second);
        }
        bool end_in_this_round = false;
        while (1) {
            if (queue1.empty())return time_count;//queue1.top() == 1表明即将执行最后一轮
            if (queue1.top() == 1)end_in_this_round = true;
            for (int i = 0; i <= n; ++i) {//循环n+1次因为只要不退出，每轮必消耗n+1单位时间
                ++time_count;
                if (!queue1.empty()) {//queue1中的任务执行一次，保存到queue2中
                    if (queue1.top() > 1)queue2.push(queue1.top() - 1);
                    queue1.pop();
                }
                else {
                    if (end_in_this_round)return time_count - 1;
                }
            }
            while (!queue1.empty()) {
                queue2.push(queue1.top());//将未执行的任务搬运到queue2
                queue1.pop();
            }
            swap(queue1, queue2);//交换引用
        }
    }
};
int main(){
   int n;
   vector<char> task;
   char s;
   cin>>n;
   int i=0;
   while(i<6){
    cin>>s;
    task.push_back(s);
    i=i+1;
   }
   Solution sk;
   int time1=sk.leastInterval(task,n);
   cout<<time1;
}