专栏首页健程之道力扣621——任务调度器

力扣621——任务调度器

这道题主要是找规律,优化的时候可以采用贪心算法的思想。

原题

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务,或者在待命状态。

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

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

示例 1:

输入: tasks = ["A","A","A","B","B","B"], n = 2
输出: 8
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.

注:

  1. 任务的总个数为 [1, 10000]。
  2. n 的取值范围为 [0, 100]。

原题url:https://leetcode-cn.com/problems/task-scheduler/

解题

找规律

这道题的思路,正向推导的话,其实就是优先排出现次数多的任务,根据间隔 n ,填充任务,直到所有任务的次数最终都减为0。

因此,我们可以用数组存储任务的总次数(因为用大写英文字母表示任务,那就代表最多只能有26种任务),排序之后,按照间隔 n ,从大到小取任务,取完后,再对数组排序,重复上述取任务的过程,直到数组的最大值为0。

接下来我们看看代码:

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        // 将task放入数组中
        int[] countArray = new int[26];
        for (char task: tasks) {
            countArray[task - 'A']++;
        }
        // 从小到大,进行排序
        Arrays.sort(countArray);
        // 最终耗时
        int time = 0;
        // 从大到小开始遍历
        while (countArray[25] > 0) {
            // 每次遍历前n个数
            int i = 0;
            while (i <= n) {
                // 说明所有任务已经执行完成
                if (countArray[25] == 0) {
                    break;
                }
                // 遍历
                if (i < 26 && countArray[25 - i] > 0) {
                    countArray[25 - i]--;
                }
                // 耗时+1
                time++;
                // 更换任务
                i++;
            }
            // 从小到大排序
            Arrays.sort(countArray);
        }
        return time;
    }
}

提交OK,但执行时间上确实不太好,只打败了47.62%的 java 执行时间,其时间复杂度为O(time), time 代表最终的执行时间。

贪心算法

我们再来想想这道题,影响最终执行时间的,有两个因素,一个是任务中出现的最大次数,另一个就是间隔 n 了。

如果我们站在最多任务的角度,来看这个问题,假设其最大次数为 maxCount,那么该任务所需的最短执行时间为(maxCount - 1) * (n + 1) + 1,如果还有其他 i 个和 maxCount 相同次数的任务,那么需要在最终的结果上再加上 i。

那么上面求出来的就是正确答案了吗?

并不是,因为上面的最短时间,是当剩余时间片能够塞满任务数小于 maxCount 的所有任务。假设 n 很小,那么剩余任务肯定需要在任务数等于 maxCount 的那些任务执行完之后,还要继续执行。

但因为最大任务已经可以满足在间隔时间内执行完,那么出现次数小于 maxCount 的任务,肯定可以连续执行完成的,也就是不需要空闲等待时间。那么此时的最短执行时间也就是总任务数了。

接下来我们看看代码:

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        if (tasks.length == 0 || n == 0) {
            return tasks.length;
        }

        // 将task放入数组中
        int[] countArray = new int[26];
        for (char task : tasks) {
            countArray[task - 'A']++;
        }
        // 从小到大,进行排序
        Arrays.sort(countArray);
        // 获取最大次数
        int maxCount = countArray[25];
        // 如果其他次数都比maxCount小的话,求出针对maxCount的最短时间
        int result = (maxCount - 1) * (n + 1);
        // 遍历countArray
        for (int i = 25; i >= 0; i--) {
            // 如果有和maxCount相同的,则执行时间+1
            if (countArray[i] == maxCount) {
                result++;
            }
            // 否则,直接结束
            else {
                break;
            }
        }

        // 如果总任务数比理论上的最短时间长,说明任务很多,但可以把每个桶填满,因此最短时间也就是总任务数
        return Math.max(result, tasks.length);
    }
}

提交OK ,在所有 Java 提交中击败了100.00%的用户,确实快了很多。其时间复杂度为O(M),M 代表总任务数。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要是找规律,优化的时候可以采用贪心算法的思想。

本文分享自微信公众号 - 健程之道(JianJianCoder),作者:健健壮

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 621. 任务调度器(贪心)

    给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可...

    Michael阿明
  • Quartz任务调度器

    这里加入的是quartz-1.8.6版本。Quart的官网:http://www.quartz-scheduler.org/;项目中的框架的spring是spr...

    intsmaze-刘洋
  • 任务调度利器:Celery

    Celery是Python开发的分布式任务调度模块,今天抽空看了一下,果然接口简单,开发容易,5分钟就写出了一个异步发送邮件的服务。

    小小科
  • 任务调度利器:Celery

    Celery是Python开发的分布式任务调度模块,今天抽空看了一下,果然接口简单,开发容易,5分钟就写出了一个异步发送邮件的服务。 Celery本身不含消息...

    小小科
  • C# 任务调度神器 FluentScheduler

    最近几天在写一些自动执行的程序,按照古老的做法就是做成exe可执行文件,并且在任务执行完自动退出。然后用Windows的Task Scheduler按照要求设置...

    Tony老师
  • 【小家Spring】Spring任务调度核心接口(类)之---TaskScheduler(任务调度器)、Trigger(触发器)、ScheduledTask(调度任务)详解

    先推荐阅读此篇: 【小家java】Java定时任务ScheduledThreadPoolExecutor详解以及与Timer、TimerTask的区别(执行指...

    YourBatman
  • 任务调度器 (难度:中等) - Day20201205

    给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在 1 个单...

    前端小书童
  • 任务调度SpringTask

    在企业级应用中,经常会制定一些“计划任务”,即在某个时间点做某件事情,核心是以时间为关注点,即在一个特定的时间点,系统执行指定的一个操作。常见的任务调度框架有Q...

    一点博客
  • FreeRTOS 任务调度 任务创建

    FreeRTOS 的任务调度在 Source/include/task.c 中实现,包含了任务的创建、切换、挂起、延时和删除等所有功能。涉及到的链表组织见文章 ...

    orientlu

扫码关注云+社区

领取腾讯云代金券