Task Scheduler

发表于 | 分类于

Task Scheduler

题目描述：

给定一个计算机执行任务的数组(用’A’-‘Z’表示，且不必按照字母序执行)，和一个执行相同任务的间隔n,表示执行相同两个任务之间最少需要有n个时间间隔，一个时间间隔内只能执行一个任务。

例子：

具体描述见LeetCode621

解题思路：

这边的思路主要是逆序的思维；我们找到所有字符任务中出现最多次数的字符，假设为A有7个；我们对6个A进行任务排序的情况下，不管其他字符是什么情况，我们最少需要的间隔是6 * n个字符；而后将剩下的最后一个A进行排序，因为其他的字符可能也是7个，所以需要找到剩下字符也是7个的字符个数将其加到最后结果中即可。这边需要注意的是，如果间隔是0的情况下：举个例子[“A”,”A”,”A”,”B”,”B”,”B”]，间隔为0，根据以上计算过程得到的4；但是实际上需要的是6个，即再怎么排序得到的结果不会少于所有任务数。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int count = 0;
        unordered_map<char, int> hash;
        for (auto e: tasks){
            hash[e]++;
            count = max(count, hash[e]);
        }//找到出现最多的任务数和得到哈希表
        int res = (count - 1) * (n + 1);
        //对前count-1个字符进行排列
        for (auto i : hash){
            if (i.second == count) res++;
        }//找到出现字符数也是count的字符
        return max((int)tasks.size(), res);
    }
};