java开发环境变量 ipv4 k8s sorting validation keras angularjs版本 vue组件注册 vue添加class jq获取第一个子元素 jquery绑定事件的方法 coreldraw入门学习 java 大文件上传 python配置环境 java日期 java8特性 randomjava java数组删除 java字符串替换 java删除文件 java读取文件 java接口调用 linux安装系统 tabletpc qtp下载 飞猪ip 视频字幕提取器 dll之家 js关闭当前页面 谷歌地球怎么用不了 cad圆变成多边形 聊呗电脑版 pr怎么旋转视频画面 思源字体包 剪影的意思 myeclipse J9 苹果商店怎么换地区 东方通达信 制作柏拉图的简易步骤
当前位置: 首页 > 学习教程  > 编程语言

【LeetCode】621. Task Scheduler 任务调度器(Medium)(JAVA)

2020/12/5 9:38:03 文章标签:

【LeetCode】621. Task Scheduler 任务调度器(Medium)(JAVA) 题目地址: https://leetcode.com/problems/diameter-of-binary-tree/ 题目描述: Given a characters array tasks, representing the tasks a CPU needs…

【LeetCode】621. Task Scheduler 任务调度器(Medium)(JAVA)

题目地址: https://leetcode.com/problems/diameter-of-binary-tree/

题目描述:

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.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.

Example 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: 
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

Constraints:

  • 1 <= task.length <= 104
  • tasks[i] is upper-case English letter.
  • The integer n is in the range [0, 100]

题目大意

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

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

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

提示:

  • 1 <= task.length <= 104
  • tasks[i] 是大写英文字母
  • n 的取值范围为 [0, 100]

解题方法

AAAAABBBBCCDDEFG
n = 3

1. ABCDEFG
2 .ABCD
3. AB
4. AB
5. A

// 调整后
1. ABCD
2. ABCD
3. ABEF
4. ABG
5. A
  1. 因为 task[i] 只包含大写英文字母,就可以用一个长度 26 的一位数组来表示每个字母的出现次数
  2. 遍历一次计数的数组,先把所有不同的字母取一遍,不断循环,直到没有字母剩下位置,然后组成不同的队列,就像上面实例一样,有 5 个队列
  3. 可以看到队列的性质,总是字母多的在上一排,而且下一排有的字母上一排肯定有,上一排有的下一排不一定有
  4. 根据队列的性质,我们可以把上一排多余的字母分给不够的一排,然后再计算对于冷却是否满足
  5. 所以可以把每一列多退少补的特性,计算要补上的个数: res += n + 1 - curCount; note: 退的个数可能是多余要补的个数的,所以 res >= 0
  6. note: 这里举得例子是字母顺序越靠前个数越多,实际上跟这没关系,我们也可以取出后进行排序,把个数多的排在前面,个数少的排在后面,这样和例子结果就一样了
  7. note: 最后一个就不需要管了,因为最后一个的后面已经不需要冷却了
class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] chCount = new int[26];
        for (int i = 0; i < tasks.length; i++) {
            chCount[tasks[i] - 'A']++;
        }
        int count = 0;
        int res = 0;
        while (count < tasks.length) {
            int curCount = 0;
            for (int i = 0; i < chCount.length; i++) {
                if (chCount[i] <= 0) continue;
                curCount++;
                count++;
                chCount[i]--;
            }
            if (count < tasks.length) res += n + 1 - curCount;
        }
        res = Math.max(0, res);
        return res + tasks.length;
    }
}

执行耗时:2 ms,击败了97.81% 的Java用户
内存消耗:39.7 MB,击败了78.37% 的Java用户

欢迎关注我的公众号,LeetCode 每日一题更新

本文链接: http://www.dtmao.cc/news_show_450043.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?