当前位置: 首页 > 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;包括烟头测试和利用乙炔火焰模拟…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

uni-app学习笔记三十五--扩展组件的安装和使用

由于内置组件不能满足日常开发需要&#xff0c;uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件&#xff0c;需要安装才能使用。 一、安装扩展插件 安装方法&#xff1a; 1.访问uniapp官方文档组件部分&#xff1a;组件使用的入门教程 | uni-app官网 点击左侧…...