Meng

621. Task Scheduler

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks. Example

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

题意：这个题是说cpu一次可以执行一个任务，但是相同两个任务必须相隔 $n$ 个interval。 问多少个inteval可以把所有任务做完。 这个题可以用冷冻queue来做，详见leetcode小结。 代码如下

代码

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] map = new int[26];
        for (char c: tasks)
            map[c - 'A']++;
        PriorityQueue < Integer > queue = new PriorityQueue < > (26, Collections.reverseOrder());
        for (int f: map) {
            if (f > 0)
                queue.add(f);
        }
        int time = 0;
        while (!queue.isEmpty()) {
            int i = 0;
            List < Integer > temp = new ArrayList < > ();
            while (i <= n) {
                if (!queue.isEmpty()) {
                    if (queue.peek() > 1)
                        temp.add(queue.poll() - 1);
                    else
                        queue.poll();
                }
                time++;
                if (queue.isEmpty() && temp.size() == 0)
                    break;
                i++;
            }
            for (int l: temp)
                queue.add(l);
        }
        return time;
    }
}

第二个解法比较有意思。 我们计算出执行任务所需要的 interval 和 idle 的 interval， 然后相加即可。 首先对任务进行计数，按照 frequency 次数从小到大排序。 其中最多任务的那一个记为 $max$， 然后和 $n$ 相乘即可得出完成任务且每个任务相间 $n$ 的总时间。因为最后一组任务不需要 idle 补充，那么计算 idle 的时候，需要把最后一行去掉。 变成 $(max - 1) * n $。 然后我们需要从后往前遍历，用 $max - 1$ 减去排好的task的个数，剩下的就是 idle 的个数。 最后把他们相加起来。原文链接 如图所示： here

代码

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] map = new int[26];
        for (char c: tasks)
            map[c - 'A']++;
        Arrays.sort(map);
        int max_val = map[25] - 1, idle_slots = max_val * n;
        for (int i = 24; i >= 0 && map[i] > 0; i--) {
            idle_slots -= Math.min(map[i], max_val);
        }
        return idle_slots > 0 ? idle_slots + tasks.length : tasks.length;
    }
}

Search

    Table of Contents