当前位置: 首页 > news >正文

【优先级队列】任务分配

任务分配问题,有n个任务,每个任务有个达到时间。将这些任务分配给m个处理器,进行处理。每个处理器的处理时间不一样。处理器的任务列表有最大任务数限制。
分配任务的策略是:当前待分配的任务的处理时刻最小。如果处理时刻相同,处理器id小的优先。
假设从时刻0开始分配任务和处理任务。在某一时刻,要求处理器先标记任务的完成状态,再接受新的任务。
问所有问题处理完毕后的时刻是多少?

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <string>
#include <queue>
using namespace std;class Solution
{
public:int Dispatch(vector<int> timeUnit, vector<int> arriveTimeList, int queueLen){int n = timeUnit.size();this->timeUnit = timeUnit;this->queueLen = queueLen;taskTime.resize(n, 0);taskCount.resize(n, 0);auto cmp = [&] (int x, int y) -> bool {if (taskCount[x] == queueLen && taskCount[y] == queueLen) {return x > y;}if (taskCount[x] == queueLen) {return true;}if (taskCount[y] == queueLen) {return false;}int time1 = taskTime[x] + timeUnit[x] * taskCount[x];int time2 = taskTime[y] + timeUnit[y] * taskCount[y];if (time1 == time2) {return x > y;}return time1 > time2;};int j = 0;int curTime = 0;for (; ; curTime++) {priority_queue<int, vector<int>, function<bool(int,int)>> q(cmp);// 出队for (int i = 0; i < n; i++) {if (taskCount[i] == 0) {q.push(i);continue;}int cnt = (curTime - taskTime[i]) / timeUnit[i];taskCount[i] -= cnt;if (taskCount[i] < 0) {taskCount[i] = 0;taskTime[i] = 0;} else {taskTime[i] += cnt * timeUnit[i];}q.push(i);}int task = q.top();// 入队,直到不能再加了while (j < arriveTimeList.size() && arriveTimeList[j] <= curTime && taskCount[task] < queueLen) {q.pop();taskCount[task]++;if (taskCount[task] == 1) {taskTime[task] = curTime;}j++;q.push(task);task = q.top();}if (j == arriveTimeList.size()) {break;}}int ans = 0;for (int i = 0; i < n; i++) {ans = max(ans, taskTime[i] + taskCount[i] * timeUnit[i]);}return ans;}
private:vector<int> taskTime;vector<int> taskCount;vector<int> timeUnit;int queueLen;
};int main(int argc, char *argv[])
{vector<int> timeUnit = {1, 2, 3, 4, 5};vector<int> arriveTimeList = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7};int rightAns = 5;Solution s;int ans = s.Dispatch(timeUnit, arriveTimeList, 3);cout << "ans: " << ans << endl;return 0;
}

相关文章:

【优先级队列】任务分配

任务分配问题&#xff0c;有n个任务&#xff0c;每个任务有个达到时间。将这些任务分配给m个处理器&#xff0c;进行处理。每个处理器的处理时间不一样。处理器的任务列表有最大任务数限制。 分配任务的策略是&#xff1a;当前待分配的任务的处理时刻最小。如果处理时刻相同&am…...

设计模式之适配模式是什么?以及在Spring AOP中的拦截器链的使用源码解析。

前言 本文涉及到适配模式的基本用法&#xff0c;以及在Spring AOP中如何使用&#xff0c;首先需要了解适配模式的工作原理&#xff0c;然后结合Spring AOP的具体实现来详细详细解析源码。 首先&#xff0c;适配模式&#xff0c;也就是Adapter Pattern&#xff0c;属于结构型设计…...

Python 库自制 Cross-correlation 算法

Python 库自制 Cross-correlation 算法 引言正文引言 虽然 Scipy 库中包含了成熟的 Cross-correlation 算法,但是有些时候我们无法使用现成的库进行数据处理。这里介绍如何使用 Python 基础函数自制 Cross-correlation 算法。后续读者可以将该算法转换为其他各类语言。 正文…...

C++(23):为类成员函数增加this参数

C23允许指定类成员函数的第一个参数的this类型&#xff0c;从而更加便于函数重载&#xff1a; #include <iostream> using namespace std;class A{ public:void func(this A&){cout<<"in func1"<<endl;}void func(this const A&){cout<…...

javaSE学习笔记23-线程(thread)-总结

创建线程的三种方式 练习代码 package com.kuang.thread;import java.util.concurrent.Callable; import java.util.concurrent.ExecutionException; import java.util.concurrent.FutureTask;//回顾总结线程的创建 public class ThreadNew {public static void main(String[…...

【DeepSeek服务器部署全攻略】Linux服务器部署DeepSeek R1模型、实现API调用、搭建Web页面以及专属知识库

DeepSeek R1模型的Linux服务器搭建、API访问及Web页面搭建 1&#xff0c;引言2&#xff0c;安装Ollama工具3&#xff0c;下载DeepSeek R1 模型4&#xff0c;DeepSeek命令行对话5&#xff0c;DeepSeek API接口调用6&#xff0c;DeepSeek结合Web-ui实现图形化界面远程访问6.1&…...

【JAVA工程师从0开始学AI】,第四步:闭包与高阶函数——用Python的“魔法函数“重构Java思维

副标题&#xff1a;当严谨的Java遇上"七十二变"的Python函数式编程 历经变量战争、语法迷雾、函数对决&#xff0c;此刻我们将踏入Python最迷人的领域——函数式编程。当Java工程师还在用接口和匿名类实现回调时&#xff0c;Python的闭包已化身"智能机器人"…...

算法日记20:SC72最小生成树(prim朴素算法)

一、题目&#xff1a; 二、题解 2.1&#xff1a;朴素prim的步骤解析 O ( n 2 ) O(n^2) O(n2)(n<1e3) 0、假设&#xff0c;我们现在有这样一个有权图 1、我们随便找一个点&#xff0c;作为起点开始构建最小生成树(一般是1号)&#xff0c;并且存入intree[]状态数组中&#xf…...

玩转SpringCloud Stream

背景及痛点 现如今消息中间件(MQ)在互联网项目中被广泛的应用&#xff0c;特别是大数据行业应用的特别的多&#xff0c;现在市面上也流行这多个消息中间件框架&#xff0c;比如ActiveMQ、RabbitMQ、RocketMQ、Kafka等&#xff0c;这些消息中间件各有各的优劣&#xff0c;但是想…...

嵌入式经常用到串口,如何判断串口数据接收完成?

说起通信&#xff0c;首先想到的肯定是串口&#xff0c;日常中232和485的使用比比皆是&#xff0c;数据的发送、接收是串口通信最基础的内容。这篇文章主要讨论串口接收数据的断帧操作。 空闲中断断帧 一些mcu&#xff08;如&#xff1a;stm32f103&#xff09;在出厂时就已经在…...

iOS App的启动与优化

App的启动流程 App启动分为冷启动和热启动 冷启动&#xff1a;从0开始启动App热启动&#xff1a;App已经在内存中&#xff0c;但是后台还挂着&#xff0c;再次点击图标启动App。 一般对App启动的优化都是针对冷启动。 App冷启动可分为三个阶段&#xff1a; dyld&#xff1a…...

导出指定文件夹下的文件结构 工具模块-Python

python模块代码 import os import json import xml.etree.ElementTree as ET from typing import List, Optional, Dict, Union from pathlib import Path class DirectoryTreeExporter:def __init__(self,root_path: str,output_file: str,fmt: str txt,show_root: boo…...

Leetcode - 周赛436

目录 一、3446. 按对角线进行矩阵排序二、3447. 将元素分配给有约束条件的组三、3448. 统计可以被最后一个数位整除的子字符串数目四、3449. 最大化游戏分数的最小值 一、3446. 按对角线进行矩阵排序 题目链接 本题可以暴力枚举&#xff0c;在确定了每一个对角线的第一个元素…...

【pytest】编写自动化测试用例命名规范README

API_autoTest 项目介绍 1. pytest命名规范 测试文件&#xff1a; 文件名需要以 test_ 开头或者以 _test.py 结尾。例如&#xff0c;test_login.py、user_management_test.py 这样的命名方式&#xff0c;pytest 能够自动识别并将其作为测试文件来执行其中的测试用例。 测试类…...

Compose常用UI组件

Compose常用UI组件 概述Modifier 修饰符常用Modifier修饰符作用域限定Modifier Modifier 实现原理Modifier.Element链的构建链的解析 常用基础组件常用布局组件列表组件 概述 Compose 预置了很多基础组件&#xff0c;如 Button&#xff0c;TextField&#xff0c;TopAppBar等&a…...

斐波那契数列模型:在动态规划的丝绸之路上追寻斐波那契的足迹(上)

文章目录 引言递归与动态规划的对比递归解法的初探动态规划的优雅与高效自顶向下的记忆化搜索自底向上的迭代法 性能分析与比较小结 引言 斐波那契数列&#xff0c;这一数列如同一条无形的丝线&#xff0c;穿越千年时光&#xff0c;悄然延续其魅力。其定义简单而优美&#xff…...

Hackthebox- Season7- Titanic 简记 [Easy]

简记 ip重定向到 http://titanic.htb,先添加hosts 收集子域名 wfuzz -c -u http://titanic.htb/ -w /usr/share/seclists/Discovery/DNS/subdomains-top1million-20000.txt -H Host:FUZZ.titanic.htb --hl 9 ******************************************************** * Wfu…...

Sa-Token 根据官方文档简单实现登录认证的示例

Sa-Token 根据官方文档实现登录鉴权测试 功能实现步骤依赖配置文件启动类创建 controller启动项目测试不用密码登录查看cookie状态 密码登录查看cookie状态 修改token名称 Apipost 测试无 cookie 模式【使用 token】后端将 token 返回到前端修改代码&#xff1a;测试&#xff1…...

rustdesk编译修改名字

最近&#xff0c;我用Rust重写了一个2W行C代码的linux内核模块。在此记录一点经验。我此前没写过内核模块&#xff0c;认识比较疏浅&#xff0c;有错误欢迎指正。 为什么要重写&#xff1f; 这个模块2W行代码量看起来不多&#xff0c;却在线上时常故障&#xff0c;永远改不完。…...

BS5852英国家具防火安全条款主要包括哪几个方面呢?

什么是BS5852检测&#xff1f; BS5852是英国针对家用家具的强制性安全要求&#xff0c;主要测试家具在受到燃烧香烟和火柴等火源时的可燃性。这个标准通常分为四个部分进行测试&#xff0c;但实际应用中主要测试第一部分和第二部分&#xff0c;包括烟头测试和利用乙炔火焰模拟…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践

01技术背景与业务挑战 某短视频点播企业深耕国内用户市场&#xff0c;但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大&#xff0c;传统架构已较难满足当前企业发展的需求&#xff0c;企业面临着三重挑战&#xff1a; ① 业务&#xff1a;国内用户访问海外服…...

Axure Rp 11 安装、汉化、授权

Axure Rp 11 安装、汉化、授权 1、前言2、汉化2.1、汉化文件下载2.2、windows汉化流程2.3、 macOs汉化流程 3、授权 1、前言 Axure Rp 11官方下载链接&#xff1a;https://www.axure.com/downloadthanks 2、汉化 2.1、汉化文件下载 链接: https://pan.baidu.com/s/18Clf…...