1、概述

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

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

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

示例 1：

输入：tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2

输出：8

解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
 在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。 
示例 2：

输入：tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 0

输出：6

解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0

[“A”,”A”,”A”,”B”,”B”,”B”]

[“A”,”B”,”A”,”B”,”A”,”B”]

[“B”,”B”,”B”,”A”,”A”,”A”]

…

诸如此类

示例 3：

输入：tasks = [“A”,”A”,”A”,”A”,”A”,”A”,”B”,”C”,”D”,”E”,”F”,”G”], n = 2

输出：16

解释：一种可能的解决方案是：
 A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A
提示：

1 <= task.length <= 104

tasks[i] 是大写英文字母

n 的取值范围为 [0, 100]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/task-scheduler

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、思路

3、解题

class Solution {
    /**
     * @param String[] $tasks
     * @param Integer $n
     * @return Integer
     */
    function leastInterval($tasks, $n) {
        /**思路2**/
        $count = count($tasks);
        $array = array_count_values($tasks);
        $max_num = max($array);
        $array2 = array_count_values($array);
        $rep_num = $array2[$max_num];
        $num = ($max_num - 1) * ($n + 1) + $rep_num;
        return max($count, $num);
        /**思路1**/
        // if ($n == 0) {
        //     return count($tasks);
        // }
        // $array = array_count_values($tasks);
        // $result = [];
        // $array_is_join = [];//保存是否可插入状态
        // while (count($array) > 0) {
        //     arsort($array);
        //     $join = false;//记录是否插入数据
        //     $join_value = null;//记录插入的值
        //     //判断是否可插入任务
        //     foreach ($array as $key => $value) {
        //         if (!isset($array_is_join[$key]) || $array_is_join[$key] >= $n) {
        //             $result[] = $key;
        //             $array[$key]--;
        //             if ($array[$key] == 0) {
        //                 unset($array[$key]);
        //             }
        //             $join = true;
        //             $join_value = $key;
        //             break;
        //         }
        //     }
        //     //未插入任务的话加入待命状态
        //     if (!$join) {
        //         $result[] = 0;//0表示待命状态
        //     }
        //     //所有任务距离加1
        //     $array_is_join = array_map(function ($v) {
        //         return $v + 1;
        //     }, $array_is_join);
        //     //新处理任务距离置0
        //     if ($join_value !== null) {
        //         $array_is_join[$join_value] = 0;
        //     }
        // }
        // return count($result);
    }
}

算法

621. 任务调度器

1、概述

2、思路

3、解题