621. Task Scheduler - Medium

前往題目

之前寫的文章

有難度的一題

思路

很重要的觀念是task的頻率由大到小，每次取前n個來排，也就是說假設今天是n=2，然後有A出現5次，B出現3次，C出現1次，那就是取AB，然後A和B各減1。這樣可以保證最少次數的Idle，不然先把小頻率的都取完了，之後為了滿足條件就必須每次都放n — 1個Idle，就不是最小單位時間了

1. priority queue(pq)來儲存每個task的頻率，由大到小
2. 在pq裡，取n或是pq.size()當作k，看誰比較小，因為取到比較大的那個，會導致pq沒有item或是取超出n個item
3. 取出k個之後，每個任務頻率做相應的減去
4. 如果還不是最後一輪，就加上n個，因為每個區間要n個；如果是最後一輪，加上k，因為不需要再Idle了
5. 還有task的話再塞回去pq裡面進行下一輪的安排

Code

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

        // 儲存任務與任務次數
        for (char task : tasks) {
            map.put(task, map.getOrDefault(task, 0) + 1);
        }

        // 頻率由高到低
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());

        for (Map.Entry<Character, Integer> a: map.entrySet()) {
            pq.add(a.getValue());
        }

        // A series of n different tasks
        ++n;
        int res = 0;

        // Each round
        while (!pq.isEmpty()) {
            // Remaining tasks to arrange
            int k = Math.min(n, pq.size());

            List<Integer> temp = new ArrayList<>();

            // Schedule k tasks
            for (int i = 0; i < k; ++i) {
                int f = pq.poll();
                --f;
                if (f != 0)
                    // Add to temp for next round if the task hasn't finished
                    temp.add(f);
            }
            
            // Still have more tasks, so tasks with idles
            if (!temp.isEmpty()) {
                res += n;
            } else {
                // Last round, add the rest, no need idle
                res += k;
            }

            // Update frequencies, preparing for the next round
            for (int i : temp) {
                pq.offer(i);
            }
        }
        return res;
    }
}