【leetcode热题Hot100】——任务调度器

• 个人主页:努力学习的少年
• 🤟 版权: 本文由【努力学习的少年】原创、在CSDN首发、需要转载请联系博主
• 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦

一.题目

1.题目描述

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中 每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且 每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者 处于待命状态。

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

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

示例 1：

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。

示例 2：

输入：tasks = ["A","A","A","B","B","B"], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]

...
诸如此类

示例3：

输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
输出：16
解释：一种可能的解决方案是：

A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A

提示：

• 1 <= task.length <= 104
• tasks[i] 是大写英文字母
• n 的取值范围为 [0, 100]

2.原始框架

class Solution {

public:

    int leastInterval(vector<char>& tasks, int n) {


    }

};

3.原题链接

621. 任务调度器

二.解题报告

1.思路

• 因为 n 是相同两个任务执行的冷却时间，也就是说，在time秒中执行了A任务，则time+n秒内就不能再执行A任务。
• 如果相同的任务堆积在一起运行，则待命的时间就越长，因为它们之间运行有冷却时间，因此，为了保证运行时间较短，我们需要将最多的任务先给消耗掉，也就是先让它运行，防止堆积在末尾。

例如：

tasks = ["A","A","A","A","A","A","B","B","B","E","F","G"]任务，n=2，其中任务A它的数量是最多的，其次是B任务，那么我们就需要先消耗掉A任务，其次是B任务，任务A的它执行的时间线：A->.....->A->......->A->......->A->.......->A..., 我们可以在A任务的冷却时间中穿插着不同的任务，因此有：A->B->E->A->B->F->A->B->G->A->(待命）->(待命）->A->(待命）->(待命）->A.

如果不先消耗掉较多的相同的任务，而是先消耗掉较少的任务数量，那么最后相同的任务就会堆积到一起，导致运行效率较低。例如：

E->F->G->B->(待命）->(待命）->B->(待命）->(待命）->B->(待命）->(待命）->B->A->(待命）->(待命）->A->(待命）->(待命)->A->(待命）->(待命）->A->(待命）->(待命）....

从上面的例子可以看到，如果相同的任务堆积在一起运行，则待命的时间就越多，因此，我们就需要先将较多的任务给消耗掉。

• 由于是任务类型是大写字母，所以我们可以创建一个26位大小的来存储相同任务的数量，其中数组的下标表示任务类型，存储的内容是任务的数量。
•  创建一个大根堆来表示就绪队列，它是以任务的相同的任务为基准，数量最多的任务存放在堆的根节点。
• 再一个小根堆来表示冷却队列，它是以任务执行的时间为基准，时间最早的任务存放在堆的根节点。
• cpu开始执行时，定义一个时间time并初始为0，记录时间，之后每次执行或者待命，time就++。
• 就先从冷却队列中的根节点判断是否有 执行的时间+冷却时间<当前时间的，如果有，则将冷却队列中的 根节点的任务 和 该任务的数量 存放到就绪队列中。
• 然后cpu再从就绪队列中拿出根节点的任务，该任务的数量--，并将该任务从就绪队列中拿走，进入冷却时间，将它 执行的time 和 该任务 存放进冷却队列中。
• 直到冷却队列和就绪队列中没有任务，则执行完毕，最终的time就为最短的时间。

 

 2.代码详解

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        using pii=pair<int,int>;
        priority_queue<pii> pq1;//就绪队列
        priority_queue<pii,vector<pii>,greater<pii>> pq2;//冷却队列

        int arr[26]={0};
        //数组0下标代表的是任务A，1下标是任务B
        //以此类推，25下标则代表的是任务Z
        for(auto ch:tasks){
            //统计所有任务的次数
            arr[ch-'A']++;
        }
        
        for(int i=0;i<26;i++){
            //将任务次数不为0放进就绪队列中
            if(arr[i]!=0)
            pq1.push(pii(arr[i],i));
        }

        int time=0;
        while(!pq1.empty()||!pq2.empty()){
            
            if(!pq2.empty()&&pq2.top().first+n<time){
                //将冷却好的任务和它的任务次数放进就绪队列中
                int  ch=pq2.top().second;
                pq1.push(pii(arr[ch],ch));
                pq2.pop();
            }

            if(!pq1.empty()){
                int ch=pq1.top().second;
                arr[ch]--;
                if(arr[ch]!=0)//任务次数不为0的任务放进冷却队列中
                pq2.push(pii(time,ch));
                pq1.pop();
            }
            time++;//时间++
        }
        return time;
    }
};

3.总结

priority_queue<类型>默认是大根堆，如果想要使用小根堆，需要在模板类型中多加一个greater<类型>的反函数，由于模板初始值，是从左往右初始的，因此前面的容器vector<类型>就不能省略,,因此，小根堆的类型为 priority_queue<类型，容器，greater<类型>>