LeetCode621 任务调度器

发表于 | 分类于 |
字数统计: 413 | 阅读时长 ≈ 1

链接: https://leetcode-cn.com/problems/task-scheduler/

题意

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。两个相同种类的任务之间必须有长度为整数 n 的冷却时间，计算完成所有任务所需要的最短时间 。

解法

一开始考虑模拟，然后发现情况不对
实现起来有点复杂
对于策略也不是很确定
看了题解才明白了这道题的奥义
考虑对最多任务数量的任务A建立桶，并且在这个桶中A是第一个任务
后面可以依次安排任务数量次多的任务B，C
剩下一些任务数量少的可以进行插空安排，如果是冷却时间内则不会产生时间上的影响

最后的结果是只需要算两个数

  1. 记录最大任务数量$N$，看一下任务数量并列最多的任务有多少个，即最后一个桶子的任务数$X$，计算 $NUM_1=(N-1)*(n+1)+x$
  2. 所有的任务数量$NUM_2$，取两者的较大值即为答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        if (n < 1) return tasks.size();
        int maxCount = 0, cnt = 0;
        vector<int> alpha(30);
        for (char c: tasks) {
            alpha[c - 'A']++;
            maxCount = max(maxCount, alpha[c - 'A']);
        }
        for (int i = 0; i < 26; i++) {
            if (alpha[i] == maxCount) cnt++;
        }
        return max((int)tasks.size(), (maxCount - 1) * (n + 1) + cnt);
    }
};