首页 > 其他分享 >力扣-621. 任务调度器

力扣-621. 任务调度器

时间:2024-06-22 19:58:32浏览次数:28  
标签:621 任务调度 优先级 周期 maxheap 力扣 任务 冷却 执行

1.题目

题目地址(621. 任务调度器 - 力扣(LeetCode))

https://leetcode.cn/problems/task-scheduler/

题目描述

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表,用字母 A 到 Z 表示,以及一个冷却时间 n。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成,但有一个限制:两个 相同种类 的任务之间必须有长度为 n 的冷却时间。

返回完成所有任务所需要的 最短时间间隔 。

 

示例 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 <= tasks.length <= 104
  • tasks[i] 是大写英文字母
  • 0 <= n <= 100

2.题解

2.1 贪心算法 + 优先级队列

思路

这题的关键思路是我们需要明白具体的贪心策略:
当处于某一个时间点,这里有若干个未被冷却的任务等待执行,我们应该优先执行那些剩余次数较多的任务
因为其余剩余次数较少的任务,我们可以穿插到其他的时间间隔进行执行,因为剩余次数少,需要插空的位置少,更容易完成,
而那些剩余次数多的任务,如果放到后面执行,可能就会面对只剩下这类任务的情况,我们执行一个该类任务,必须等待一整个时间间隔n什么都不能做

所以我们的贪心策略:优先执行当前未处于冷却状态,且剩余执行次数较多的任务
后面一个比较好解决,使用优先级队列(大根堆)即可解决,我们如何解决前面一个限制呢?

我们发现我们如果是以一个冷却周期n来划分任务执行,那么假设这个冷却周期我执行了若干任务,并执行一个从优先级队列中排除一个;
并在这个冷却周期完毕后(指第一个任务,中间其他任务尚未完成冷却),将所有本周期执行过的,被排除的任务全部装回优先级队列,并执行下一个周期;
我们可能有一个疑问,此时优先级队列中不是所有任务都冷却了(上一个周期执行的后几个任务都未冷却),我们直接放回开启新周期可以吗?

答案是可以的,在下一个周期中,我们还是按,有这么几种可能:
1.这里执行的任务上个冷却周期我没执行过(由于上一周期任务执行,部分任务执行次数减少后小于该任务,导致该任务优先级上升),那么自然没有冷却问题的
(关键!!!)2.这里执行的任务上个冷却周期我执行过(但是根据上一周期中优先级高于你的任务,你们的剩余次数同时-1,其实这一周期还是按次序还是排在你前面的,等他执行完,你也就冷却好了!!!)

所以我们就可以采用一个冷却周期一轮回的方式来解决这个问题,一个轮回中:
1.执行n+1个任务(自己执行的一次 + 冷却时间的n次),并排除优先级队列
2.执行完毕后,将这些任务放回优先级队列
3.更新总执行时间

代码

  • 语言支持:C++

C++ Code:

class Solution {
public:
    int leastInterval(std::vector<char>& tasks, int n) {
        // 统计任务出现频率
        unordered_map<char, int> taskFreq;
        for(char ch : tasks){
            if(taskFreq.count(ch)){
                taskFreq[ch]++;
            }else{
                taskFreq.emplace(ch, 1);
            }
        }

        // 使用优先级队列-维护剩余次数从大到小排列(大根堆)
        priority_queue<int> maxheap;
        for(auto p : taskFreq){
            maxheap.push(p.second);
        }

        int ans = 0;
        // 开始时间流动,每次循环一个时间冷却时间
        while(!maxheap.empty()){
            vector<int> temp;
            // 执行当前剩余次数最多的任务(一个周期:自己执行的一个间隔 + 冷却室家n)
            for(int i = 0; i < n + 1; i++){
                if(!maxheap.empty()){
                    temp.push_back(maxheap.top() - 1);
                    maxheap.pop();
                }
            }
            // 执行完一轮后,将未完成的任务放回优先级队列中
            for(int tmp : temp){
                if(tmp > 0){
                    maxheap.push(tmp);
                }
            }

            // 更新完成当前任务总的时间间隔
            // 如果栈为空,说明最后temp中的值均为0,所有任务执行完毕,加上这一部分即可
            if(maxheap.empty()){
                ans += temp.size();
            }else{
                ans += n + 1;
            }
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度:'o(w* log K),其中'N 是任务的总数量,'K 是任务种类的数量。
    对于每个任务操作,堆的操作(插入和删除)是“o(log K)”的。
  • 空间复杂度:‘’o(k)”,主要用于存储任务频率的哈希表和优先级队列。

标签:621,任务调度,优先级,周期,maxheap,力扣,任务,冷却,执行
From: https://www.cnblogs.com/trmbh12/p/18262672

相关文章

  • 190.回溯算法:组合(力扣)
    代码随想录(programmercarl.com)一、什么是回溯算法    回溯算法是一种通用的算法设计技巧,特别适用于解决组合、排列、子集等问题。它通过逐步构建解决方案,并在发现部分解决方案无效时撤销(回溯)部分计算,从而寻找所有可能的解决方案。    回溯算法的基本思......
  • 力扣每日一题 6/21 数组
    博客主页:誓则盟约系列专栏:IT竞赛专栏关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞......
  • 2022年大作业参考报告-使用C++语言开发小学生成绩管理系统、中学生成绩管理系统、大学
    背景:目录第一章需求分析   21.1   问题描述   26.1   功能需求   26.2   开发环境   26.3   开发过程   2第二章概要设计   32.1   总体设计   32.2   类的定义   32.3   接口设计   52.4  ......
  • 20240621维护记录
     dockerrun-d--namepause-1k8s.gcr.io/pause:3.2 注意:RunningError请看pods什么周期介绍https://www.jianshu.com/p/0bb8572e34f#!/bin/bashKEY=`cat/proc/sys/kernel/random/uuid`USER=`echo$KEY|cut-d"-"-f1`ACCESS_KEY=`uuidgen`SECRET_KEY=$KEYROLE_NAME......
  • 力扣-763. 划分字母区间
    题目地址(763.划分字母区间-力扣(LeetCode))https://leetcode.cn/problems/partition-labels/题目描述给你一个字符串s。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是s。返回......
  • 构建高效的大数据量延迟任务调度平台
    目录引言系统需求分析系统架构设计总体架构任务调度模块任务存储模块任务执行模块任务调度算法时间轮算法优先级队列分布式锁数据存储方案关系型数据库NoSQL数据库混合存储方案容错和高可用性主从复制数据备份与恢复故障转移性能优化水平扩展缓存机制异步处理监......
  • 任务调度框架革新:TASKCTL在Docker环境中的高级应用
    Docker:轻量级容器化技术的魅力Docker作为一款开源的轻量级容器化技术,近年来在IT界掀起了一股热潮。它通过封装应用及其运行环境,使得开发者可以快速构建、部署和运行应用。Docker的优势在于其轻量级、可移植性和可扩展性,它使得应用部署变得更加简单、快捷。TASKCTL:自动化运......
  • 力扣-452. 用最少数量的箭引爆气球
    1.题目介绍题目地址(452.用最少数量的箭引爆气球-力扣(LeetCode))https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/题目描述有一些球形气球贴在一堵用XY平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i]=[xstart,xend]......
  • 力扣每日一题 6/19 排序+动态规划
    博客主页:誓则盟约系列专栏:IT竞赛专栏关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞......
  • 力扣每日一题 6/17 枚举+双指针
    博客主页:誓则盟约系列专栏:IT竞赛专栏关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞......