Task Scheduler

題意:

給一段characters與一個整數N,characters代表是所有task要丟到CPU裡去跑,且N代表每跑N個cycle時,CPU需要休息一下,必須找出一個跑法是需要最少的cycle數。

解法:

能想到的就是貪心(Greedy)解法,希望能先把耗費最多cycle數的task先跑完,我們可以先跑一次把各個task所需的cycle數計算出來,接著使用一個MaxHeap來不斷維護當下最多cycle的task,由於我們不需要印出來跑的順序,因此只要維護剩下的cycle數即可。

這題沒有考慮到context switch的成本,因此任務之間交互跑是沒問題的,只要確保能把耗費最多cycle數的任務先跑完即可。

class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> map = new HashMap<>();
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);

        for (char c : tasks) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        queue.addAll(map.values()); 

        int cycle = 0;
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i <= n; i++) {
                if (!queue.isEmpty()) {
                    list.add(queue.remove());
                }
            }

            for (int val : list) {
                if (--val > 0) {
                    queue.offer(val);
                }
            }
            // 如何queue已空,則只需要加上當下耗費多少cycle,如果還未空,則需加上idle cycle與當下花了總共多少cycles。
            cycle += (queue.isEmpty()) ? list.size() : n + 1;
        }

        return cycle;
    }
}

Reference:

results matching ""

    No results matching ""