淘先锋技术网

首页 1 2 3 4 5 6 7

题目来源

题目描述

在这里插入图片描述
在这里插入图片描述

题目解析

思路

完成所有任务的最短时间取决于出现次数最多的任务数量

看下题目给出的例子

输入: tasks = ["A","A","A","B","B","B"], n = 2
输出: 8
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.

因为相同任务必须要有时间片为n的间隔,所以我们先把出现次数最多的任务A安排上(当然也可以选择任务B)。例子中n=2,那么任意两个任务A之间都必须间隔2个单位的时间。

A -> (单位时间) -> (单位时间) -> A -> (单位时间) -> (单位时间) -> A

中间间隔的单位时间可以用来安排别的任务,也可以出于“待命”状态。当然,为了使得总任务时间最短,我们要尽可能的把单位时间分配个其他任务。现在把b安排上:

A -> B -> (单位时间) -> A -> B -> (单位时间) -> A -> B

很容易观察到,前面两个A任务一定会固定跟着2个单位时间的间隔。最后一个A之后是否还有任务跟随取决于是否存在与任务A出现次数相同的任务

该例子的计算过程为:

(任务 A 出现的次数 - 1) * (n + 1) + (出现次数为 3 的任务个数),即:

(3 - 1) * (2 + 1) + 2 = 8

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

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

解释 (最多任务A出现的次数 - 1) * (n + 1) + (最多任务的个数) 假设是 AAABBBCC n=3

  • 第一步A _ _ _ A _ _ _A
    • 把 A _ _ _ 看成一个整体,总共有 A出现的次数-1 个
    • 每个 A _ _ _ 的长度为n个 _ _ _+一个A ,即 n+1
    • 先不管最后面的A,看第二步
  • 第二步,放入B,即A B _ _A B _ _A B
    • 细心的年轻人,应该发现了最后多了两个数A B,这正是最多任务总数的个数2 同理如果是AAABBBCCC,最后会出现ABC三个,所以最后 +最多任务的个数

然而存在一种特殊情况,例如

输入: tasks = ["A","A","A","B","B","B","C","C","D","D"], n = 2
输出: 10
执行顺序: A -> B -> C -> A -> B -> D -> A -> B -> C -> D

此时如果按照上述方法计算将得到结果为 8,比数组总长度 10 要小,应返回数组长度。为什么是数组长度呢?

  • 当算出来的结果小于数组长度,说明所有的冷却单位都被插满了,但是还有任务没被插进去。这种情况说明这个数组的任务无需冷却时间,(退化成了n=0这种情况),所以最短时间就是数组长度。
  • ps. 这种情况其实不能叫做特殊情况,而是一大类。整个题目解法存在两类:1. 任务执行过程中存在冷却这种情况。2. 不存在冷却这种情况。 【特殊情况】实际上是不存在冷却这一大类。
class Solution{
    static bool cmp(int &a, int &b){
        return a > b;
    }
public:
    int leastInterval(std::vector<char> &tasks, int n){
        if(!n){
            return tasks.size();
        }
        std::vector<int> nums(26, 0);
        for(char tast : tasks){
            nums[tast - 'A'] += 1;
        }
        std::sort(nums.begin(), nums.end(), cmp);
        int total = (n - 1) * (nums[0] - 1) + 1;
        for (int i = 1; i < nums.max_size(); ++i) {
            if(nums[i] == nums[0]){
                total++;
            }
        }
        return total > tasks.size() ? total : tasks.size();
    }
};