621.任務調度器

2020-06-12
任務調度器

給定一個用字元數組表示的 CPU 需要執行的任務列表。

其中包含使用大寫的 A - Z 字母表示的26 種不同種類的任務。

任務可以以任意順序執行，並且每個任務都可以在 1 個單位時間內執行完。CPU

在任何一個單位時間內都可以執行一個任務，或者在待命狀態。


然而，兩個相同種類的任務之間必須有長度為 n 的冷卻時間

，因此至少有連續 n 個單位時間內 CPU 在執行不同的任務，

或者在待命狀態。


你需要計算完成所有任務所需要的最短時間。

題解:
思路1：按出現次數大小排序 貪心演算法
冷卻時間n + 1為數組arr的長度 arr的第0項是出現最多次的字元 第1項是第二多次的字元 以此類推 每次確定一個字元
就把那個字元的次數-1
 
 
/**
 * @param {character[]} tasks
 * @param {number} n
 * @return {number}
 */
var leastInterval = function (tasks, n) {
  let hash = {}; // 哈希表 存tasks中有多少種字元
  hash.length = 0; // tasks的總長度
  for (let i = 0; i < tasks.length; i++) {
    hash.length++;
    if (!hash[tasks[i]]) hash[tasks[i]] = 1; // 將每一種字元出現的次數存入hash中
    else hash[tasks[i]]++;
  }

  let tmp = []; // 存每一種字元與次數的組合數組 例如：[[A, 5], [B, 3], [C, 6]...]
  Object.keys(hash).forEach(attr => {
    if (attr !== 'length')
      tmp.push([attr, hash[attr]]);
  })

  let tmpResult = [];
  while (hash.length) { // 當hash的length屬性的值大於0 進入遍歷中
    // CD時間為n 說明出現相同任務的間隔為n 也就是每一份數組的長度是n+1
    let arr = new Array(n + 1).fill(null); 
    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];
      tmp[i][1]--;
      hash.length--;
    }
    tmpResult.push(arr);
  }

  let result = [];
  // 將tmpResult合併成一個數組
  // 由於arr有可能出現最後一次有多餘的null 所以要把尾部的null都刪掉
  tmpResult.forEach(item => { result = result.concat(item) }); 
  while (result[result.length - 1] === null) result.splice(result.length - 1, 1);
  return result.length; // result的長度就是次數
};

 

Tags:

VirMach 便宜 VPS