Task Scheduler 任务调度器

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个相同种类的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B

思路

n代表了任务冷却时间，m:表示最多任务数的任务种类，length:表示最长的一个任务出现的次数。

n>0,说明同一个任务执行之后会有间隔，过了n之后相同的任务才能执行。

这就会出现2种情况：

任务彼此没有任何间隔的执行，耗时T1 = 任务总数
任务之间存在间隔，而且间隔时间无法被其他任务填满，即其他任务都被安排之后，依然存在空闲间隔的时间，耗时T2 = (length-1)*(n+1)+m

T1,T2计算后取最大。

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] cnt = new int[26];
        for (int i = 0; i < tasks.length; i++) {
            cnt[tasks[i]-'A']++;
        }
        Arrays.sort(cnt);
        int m= 0;
        for (int i = 25; i>=0&&cnt[i]==cnt[25] ; i--,m++) {

        }
        return Math.max(tasks.length,(cnt[25]-1)*(n+1)+m);
    }
}

tag

贪心,队列,数组