专栏首页前端小书童任务调度器 (难度:中等) - Day20201205

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

20201205

题目:

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

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

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

示例:

  1. 示例 1:
输入:tasks = ["A","A","A","B","B","B"], n = 2
输出:8
解释:A -> B -> (待命) -> A -> B -> (待命) -> A -> B
     在本示例中,两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间,而执行一个任务只需要一个单位时间,所以中间出现了(待命)状态。
  1. 示例 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"]
...
诸如此类
  1. 示例 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 <=
10^4
  • tasks[i] 是大写英文字母
  • n 的取值范围为 [0, 100]

抛砖引玉

思路:

简化下题意:一个数组 tasks,每个执行一个元素,相同元素至少要间隔 n 步才可以执行,返回执行完所需最小步数

抛砖引玉

要让执行步数最小则需要将待命的次数减少,则需要先找到需要执行最多次的任务,将其它任务放置到其执行的间隔中,那么如果最多次任务足够多,那么步骤数为:max*(n+1)

间隔 n 那么两个相同类型任务间隔的时间单位为:n+1

上面假设了最多次任务足够多,事实上最后一个间隔时间不一定被任务排满,那么就需要知道那种任务排在最后一个 n 周期是执行步数最少的:

  • 任务重复次数小于 max 的优先排列在最后一个之前的周期且能排列完
  • 多个任务重复次数可能都是 max,那么这个这些重复的任务需要排列在最后一个周期
/**
 * @param {character[]} tasks
 * @param {number} n
 * @return {number}
 */
var leastInterval = function(tasks, n) {
    const len = tasks.length
    if (n === 0) return len
    let max = 0,
        map = new Map(),
        maxNum = 0
    // 统计出现次数做的的任务
    for (let i = 0; i < len; i++) {
        const num = map.get(tasks[i]) || 0
        map.set(tasks[i], num + 1)
        max = Math.max(max, num + 1)
    }
    // 出现最多的任务次数可能有多个
    for (let value of map.values()) {
        if (value === max) maxNum++
    }
    // 最少执行步数
    return Math.max((max - 1) * (n + 1) + maxNum, len)
}

博客: 前端小书童

每天的每日一题,写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言

公众号:前端小书童

本文分享自微信公众号 - 前端小书童(gaowenju_web),作者:前端小书童

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

原始发表时间:2020-12-07

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Quartz任务调度器

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

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

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

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

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

    小小科
  • linux中crontab任务调度

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

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

    YourBatman
  • C# 任务调度神器 FluentScheduler

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

    Tony老师
  • 力扣621——任务调度器

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

    健程之道
  • Python中的任务调度库

    •schedule•python-crontab•APScheduler•Celery•Django Q

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

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

    Michael阿明
  • 浅析Linux中crontab任务调度

    以上所述是小编给大家介绍的Linux中crontab任务调度,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对ZaL...

    砸漏
  • Chronos:数据中心的任务调度器(job scheduler)

    大家周二好,不知不觉工作半周了。今天给大家介绍一个扩展性比较强的开源的调度程序,在研究数据中心调度的兄弟可以好好研究下。 1、Chronos来源 C...

    大数据和云计算技术
  • MySQL计划任务(事件调度器)

    MySQL5.1.x版本中引入了一项新特性EVENT,顾名思义就是事件、定时任务机制,在指定的时间单元内执行特定的任务,因此今后一些对数据定时性操作不再依赖外部...

    wangxl
  • 开源基于docker的任务调度器pipeline,比`quartzs` 更强大的分布式任务调度器

    目标: 基于docker的布式任务调度器, 比quartzs,xxl-job 更强大的分布式任务调度器。

    JadePeng
  • Python任务调度利器之APScheduler详解

    所谓的任务调度是指安排任务的执行计划,即何时执行,怎么执行等。在现实项目中经常出现它们的身影;特别是数据类项目,比如实时统计每5分钟网站的访问量,就需要每5分钟...

    砸漏
  • 在ActFramework中进行后台任务调度

    老码农
  • 服务器集群任务调度系统大比拼!

    普通刀片节点配备 两颗 Intel(R) Xeon(R) CPU E5-2692 v2 @ 2.20GHz 共24物理核,内存为64G 调度系统为 Slurm...

    生信技能树
  • Linux中的计划任务—Crontab调度重复执行的任务

    本博文的主要目的是让笔者和读者可以了解并掌握以下内容: 1、Crontab的基本概念 2、Crontab的基本组成 3、操作Crond服务 4、配置系统...

    小小工匠
  • 【STM32H7】第14章 ThreadX调度锁,任务锁和中断锁(调度阀值)

    论坛原始地址(持续更新):http://www.armbbs.cn/forum.php?mod=viewthread&tid=99514

    armfly
  • 【STM32F429】第14章 ThreadX调度锁,任务锁和中断锁(调度阀值)

    论坛原始地址(持续更新):http://www.armbbs.cn/forum.php?mod=viewthread&tid=99514

    armfly

扫码关注云+社区

领取腾讯云代金券