leetcode：621. 任务调度器

题目

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。

示例：

  1. 输入：tasks = ["A","A","A","B","B","B"], n = 2
  2. 输出：8
  3. 解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
  4.      在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
  1. 输入：tasks = ["A","A","A","B","B","B"], n = 0
  2. 输出：6
  3. 解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
  4. ["A","A","A","B","B","B"]
  5. ["A","B","A","B","A","B"]
  6. ["B","B","B","A","A","A"]
  7. ...
  8. 诸如此类
  1. 输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
  2. 输出：16
  3. 解释：一种可能的解决方案是：
  4.      A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A

解答

解法一：模拟

每次都选择不在冷却中（下次可执行时间<=time）且剩余待执行次数最大的任务，作为本次执行任务。

  • 这样才能使每种任务的剩余执行次数尽可能平均，使得 CPU 处于待命状态的时间尽可能少。

    1. class Solution {
    2. public:
    3.   int leastInterval(vector<char>& tasks, int n) {
    4.       // 哈希表，记录每种任务的频次，key = task name，val = 频次
    5.       unordered_map<char, int> freq;
    6.       for(int i = 0; i < tasks.size(); ++i)
    7.       {
    8.           if(freq.find(tasks[i]) == freq.end())
    9.               freq[tasks[i]] = 1;
    10.           else
    11.               ++freq[tasks[i]];
    12.       }
    14.       vector<int> nextValidTime;    // 记录每种任务下次可执行时间的数组
    15.       vector<int> remainTasks;    // 记录每种任务剩余待执行次数的数组
    16.       for(auto it = freq.begin(); it != freq.end(); ++it)
    17.       {
    18.           nextValidTime.push_back(1);        // 所有任务的下次可执行时间都初始化为 1
    19.           remainTasks.push_back(it->second);
    20.       }
    22.       int time = 0;        // 当前时间
    23.       int count = 0;        // 已执行的任务数
    24.       while(count < tasks.size())
    25.       {
    26.           ++time;            // 更新当前时间
    28.           int nextTask = -1;    // 下一个执行任务的下标（本轮要执行的任务序号）
    29.           int mostFreq = 0;    // 当前可执行任务的剩余待执行次数的最大值
    30.           // 选择不在冷却中（下次可执行时间<=time）且剩余待执行次数最大的任务，作为本次执行任务
    31.           for(int j = 0; j < nextValidTime.size(); ++j)
    32.           {
    33.               if(nextValidTime[j] <= time && remainTasks[j] > mostFreq)
    34.               {
    35.                   nextTask = j;
    36.                   mostFreq = remainTasks[j];
    37.               }
    38.           }
    40.           // 如果没有符合要求的任务，则当前时刻作为冷却时间
    41.           if(nextTask == -1)
    42.               continue;
    43.           // 否则，执行选择的任务
    44.           else
    45.           {
    46.               ++count;                                    // 已执行的任务数 +1
    47.               nextValidTime[nextTask] = time + n + 1;        // 更新选中任务的下次可执行时间
    48.               --remainTasks[nextTask];                    // 选中任务的剩余待执行次数 -1
    49.           }
    50.       }
    51.       return time;
    52.   }
    53. };

    复杂度分析：设任务总数 N，任务种类 M

  • 时间复杂度 O(NM)：外循环 while(count < tasks.size()) 执行的次数就是题目求的完成所有任务的最短时间，最坏情况下每次执行一个任务后都要待命 n 个时间，那么总时间为 (n +1)N，其中 n 为常数，因此时间复杂度 O(N)。内循环 for(int j = 0; j < nextValidTime.size(); ++j) 遍历每一种任务，时间复杂度 O(M)

  • 空间复杂度 O(M)：统计每种任务频次的哈希表 freq 的空间复杂度 O(M)，记录每种任务下次可执行时间的数组 nextValidTime 的空间复杂度 O(M)，记录每种任务剩余待执行次数的数组 remainTasks 的空间复杂度 O(M)

执行结果：

  1. 执行结果：通过
  3. 执行用时：108 ms, 在所有 C++ 提交中击败了 13.78% 的用户
  4. 内存消耗：33.6 MB, 在所有 C++ 提交中击败了 45.45% 的用户

解法二：填桶