621.任务调度器

2020-06-12

任务调度器

给定一个用字符数组表示的 CPU 需要执行的任务列表。

其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。

任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU

在任何一个单位时间内都可以执行一个任务，或者在待命状态。

然而，两个相同种类的任务之间必须有长度为 n 的冷却时间

，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，

或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

题解:

思路1：按出现次数大小排序 贪心算法

冷却时间n + 1为数组arr的长度 arr的第0项是出现最多次的字符 第1项是第二多次的字符 以此类推 每次确定一个字符

就把那个字符的次数-1

 

 

var leastInterval = function (tasks, n) {
  if(n === 0) return tasks.length;
  let hash = {}; // 哈希表 存tasks中有多少种字符
  let len = tasks.length; // tasks的总长度
  for (let i = 0; i < tasks.length; i++) {
    if (!hash[tasks[i]]) hash[tasks[i]] = 1; // 将每一种字符出现的次数存入hash中
    else hash[tasks[i]]++;
  }

  let tmp = Object.entries(hash); // 存每一种字符与次数的组合数组 例如：[['A', 5], ['B', 3], ['C', 6]...]

  let result = [];
  while (len) { // 当hash的length属性的值大于0 进入遍历中
    // CD时间为n 说明出现相同任务的间隔为n 也就是每一份数组的长度是n+1
    let arr = new Array(n + 1).fill(null); // 每次寻找新的arr 都要对数组tmp再次排序
    tmp.sort((a, b) => b[1] - a[1]); // tmp数组按照出现次数的多少排序 多的在最前
    // 依次取出出现最多的 第二多的 第三多的。。。放入arr中 
    // 每次遍历得出一个arr 放入tmpResult中 
    // 如果第x大的那一项不存在或者那一项的值已经是0 那么退出循环 寻找下一个arr
    for (let i = 0; i <= n; i++) {
      if (!tmp[i] || tmp[i][1] === 0) break;
      arr[i] = tmp[i][0]; // 数组的下标+1 表示当前出现次数第几多的字符
      tmp[i][1]--; // 例如A处理过一次 那么A的次数-1
      len--; // 同时 剩余未处理的长度-1
    }
    result.push(...arr);
  }
  // 由于arr有可能出现最后一次有多余的null 所以要把尾部的null都删掉
  while (result[result.length - 1] === null) result.splice(result.length - 1, 1);
  return result.length; // result的长度就是次数
};