「taskscheduler」Task Scheduler

taskscheduler

1，题目要求

Given a char array representing tasks cpu need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one Interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

example:

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

Output: 8

Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

给定一个char数组表示CPU需要做的任务。它包含大写字母A到Z，其中不同的字母代表不同的任务。任务可以没有原始订单完成。每项任务都可以在一个时间间隔内完成。对于每个间隔，CPU可以完成一个任务或只是空闲。

但是，有一个非负的冷却间隔n意味着在两个相同的任务之间，必须至少有n个间隔，CPU正在执行不同的任务或只是空闲。

您需要返回CPU将完成所有给定任务所需的最少间隔数。

2，题目思路

对于这道题，题目所给出的描述比较复杂，具体来说，就是给定一系列的计算机任务，用大写字符A-Z来表示。同时，也给出一个非负整数n，要求两个相同的任务之间必须有n个间隔，其中间隔可以是其他的任务，也可以是一个空闲idle。

给定一系列的任务以及要求的间隔n，求出完成这些任务总共需要耗费的时间。

在对题目进行分析后我们可以得知，相同任务之间（即相同字符之间）必须要有对应的隔断，且隔断数有要求。

因此，在解决这个问题时，我们的思路是：

首先，找到所有任务中，出现次数最多的任务所出现的次数。
然后，以这个次数，构建一个空白可填空的内容：
比如对于AAABBC，n=2，我们发现最大的出现次数为3，于是我们可以有：
A - - A - -
即，- 可供其他的任务（字符）插入。总长度为2*3，即 res = (maxTime - 1) * (n + 1)。
这时，我们相当于有了一个满足出现次数最多字符条件的最小长度，我们还需要向其中插入别的字符。
因为最大出现次数的字符可能不止一个字符，因此，我们还需要对之前构建的字符出现次数统计表进行一个遍历：

for(auto &tf : taskFrequence)
            if(tf == maxCount)
                res++;

在上面这个例子中会遍历到A，于是加1后有：

A - - A - - A

依次加入B和C后有：

A B C A B - A

于是，总长度为满足A字符的最小长度。

但是，还存在其他问题：
比如上面所说的最大出现次数的字符可能不止一个字符，有AAABBBCCCDDEF
这时，我们发现最大还是3，从A开始，同样地：
A - - A - -
A - - A - - A （res++）
A B - A B - A B （res++）
A B C A B C A B C （res++，此时已经没有idle了）
A B C D A B C D A B C
**A B C D E A B C D F A B C **
经过分析我们发现，此时，我们只需要按照刚才的分块形式，分别在最后插入字符，就一定不会违反题目的要求。也就是说，只要最大次数的字符满足条件，那么其他字符也可以满足条件——只要插入的位置是正确的。当然，题目只问总的长度，不问插入形式，因此，出现这种情况时，我们只需要返回给定的字符的长度即可，因此此时不需要idle。
因此，最后的返回值应该是：
max( (int)tasks.size(), res )

3，代码实现

static auto speedup = [](){
    iOS::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> taskFrequence (26, 0);
        int maxCount = -1;
        for(auto &t : tasks){
            taskFrequence[t-'A']++;
            //找到出现次数最多的任务
            maxCount = max(maxCount, taskFrequence[t-'A']);
        }
        
        int res = (maxCount-1)*(n+1);//此时，少了当前字符的最后一个字符所占的长度
        //不过后面这段循环会补回来
        for(auto &tf : taskFrequence)
            if(tf == maxCount)	//出现次数最多的字符，添加在结尾
                res++;
        
        return max((int)tasks.size(), res);
    }
};

Task Scheduler

taskscheduler

1，题目要求

2，题目思路

3，代码实现

相关阅读

栏目导航

推荐阅读

热门阅读