LeetCode_模拟_中等_621.任务调度器

淡淡的烟草味﹌ 2023-10-06 22:48 65阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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/problems/task-scheduler

## 2.思路 ##

（1）模拟

（2）构造

思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————模拟
    class Solution {
        
    	public int leastInterval(char[] tasks, int n) {
        
    	    // freq 记录每个任务出现的次数
    	    Map<Character, Integer> freq = new HashMap<>();
    	    for (char task : tasks) {
        
    	        freq.put(task, freq.getOrDefault(task, 0) + 1);
    	    }
    	    //任务种类数
    	    int m = freq.size();
    	    //计算完成所有任务所需要的最短时间
    	    int minTime = 0;
    	    List<Integer> nextValid = new ArrayList<>();
    	    List<Integer> rest = new ArrayList<>();
    	    Set<Map.Entry<Character, Integer>> entrySet = freq.entrySet();
    	    for (Map.Entry<Character, Integer> entry : entrySet) {
        
    	        int value = entry.getValue();
    	        nextValid.add(1);
    	        rest.add(value);
    	    }
    	    for (int i = 0; i < tasks.length; i++) {
        
    	        minTime++;
    	        int minNextValid = Integer.MAX_VALUE;
    	        for (int j = 0; j < m; j++) {
        
    	            if (rest.get(j) != 0) {
        
    	                minNextValid = Math.min(minNextValid, nextValid.get(j));
    	            }
    	        }
    	        minTime = Math.max(minTime, minNextValid);
    	        int best = -1;
    	        for (int j = 0; j < m; j++) {
        
    	            if (rest.get(j) != 0 && nextValid.get(j) <= minTime) {
        
    	                if (best == -1 || rest.get(j) > rest.get(best)) {
        
    	                    best = j;
    	                }
    	            }
    	        }
    	        nextValid.set(best, minTime + n + 1);
    	        rest.set(best, rest.get(best) - 1);
    	    }
    	    return minTime;
    	}
    }

//思路2————构造
    class Solution {
        
        public int leastInterval(char[] tasks, int n) {
        
            Map<Character, Integer> freq = new HashMap<Character, Integer>();
            //最多的执行次数
            int maxExec = 0;
            for (char ch : tasks) {
        
                int exec = freq.getOrDefault(ch, 0) + 1;
                freq.put(ch, exec);
                maxExec = Math.max(maxExec, exec);
            }
            //具有最多执行次数的任务数量
            int maxCount = 0;
            Set<Map.Entry<Character, Integer>> entrySet = freq.entrySet();
            for (Map.Entry<Character, Integer> entry : entrySet) {
        
                int value = entry.getValue();
                if (value == maxExec) {
        
                    ++maxCount;
                }
            }
            return Math.max((maxExec - 1) * (n + 1) + maxCount, tasks.length);
        }
    }

[Link 1]: https://leetcode.cn/problems/task-scheduler/solution/ren-wu-diao-du-qi-by-leetcode-solution-ur9w/