貪心-優先隊列-模拟-任務排程器

2020-03-10 17:22:21

問題描述：

給定一個用字元數組表示的 CPU 需要執行的任務清單。其中包含使用大寫的 A - Z 字母表示的26 種不同種類的任務。任務可以以任意順序執行，并且每個任務都可以在 1 個機關時間内執行完。CPU 在任何一個機關時間内都可以執行一個任務，或者在待命狀态。

然而，兩個相同種類的任務之間必須有長度為 n 的冷卻時間，是以至少有連續 n 個機關時間内 CPU 在執行不同的任務，或者在待命狀态。

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

示例 1：

輸入: tasks = ["A","A","A","B","B","B"], n = 2

輸出: 8

執行順序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.

注：

任務的總個數為 [1, 10000]。

n 的取值範圍為 [0, 100]。

問題求解：

解法一：貪心

從資料規模可以看出時間複雜度應該是O(n) / O(nlogn)。很容易想到的是要先将頻率計算出來，并且按照頻率進行排序，頻率最高的字元至少會占用(freq_max - 1) * (n + 1) + 1個時間周期。

如果有k個頻率均為最高，那麼上述的公式就變成了(freq_max - 1) * (n + 1) + k，在這種情況下，低頻率的字元完全放入了中間的空當中，甚至還會有盈餘。

那麼還有一種情況就是，中間的空檔并不夠放置所有剩餘的字元，那麼此時最終的解就是len(tasks)，因為剩餘的字元可以任意的插入不同slot的末尾，并且保證空閑是足夠的。

算法時間複雜度：O(nlogn)

public int leastInterval(char[] tasks, int k) {
        int n = tasks.length;
        int[] freq = new int[26];
        for (char c : tasks) freq[c - 'A'] += 1;
        Arrays.sort(freq);
        int idx = 25;
        while (idx >= 0 && freq[idx] == freq[25]) idx -= 1;
        int common = 25 - (idx + 1) + 1;
        return Math.max(n, (freq[25] - 1) * (k + 1) + common);
    }
      

　　

解法二：優先隊列

本題除了上述的貪心解法，還可以使用優先隊列去模拟結果，使用優先隊列的解更加直覺。我們每次從隊列中取k + 1個最多的任務去做，全部任務都執行完成即可。

public int leastInterval(char[] tasks, int k) {
        int n = tasks.length;
        int[] freq = new int[26];
        for (char c : tasks) freq[c - 'A'] += 1;
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < 26; i++) if (freq[i] != 0) pq.add(freq[i]);
        int res = 0;
        while (!pq.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i <= k; i++) {
                if (!pq.isEmpty()) {
                    if (pq.peek() > 1) {
                        temp.add(pq.peek() - 1);
                    }
                    pq.poll();
                }
                res += 1;
                if (pq.isEmpty() && temp.size() == 0) break;
            }
            for (Integer i : temp) pq.add(i);
        }
        return res;
    }