【优先级队列】任务分配
任务分配问题,有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;
}
相关文章:
【优先级队列】任务分配
任务分配问题,有n个任务,每个任务有个达到时间。将这些任务分配给m个处理器,进行处理。每个处理器的处理时间不一样。处理器的任务列表有最大任务数限制。 分配任务的策略是:当前待分配的任务的处理时刻最小。如果处理时刻相同&am…...
设计模式之适配模式是什么?以及在Spring AOP中的拦截器链的使用源码解析。
前言 本文涉及到适配模式的基本用法,以及在Spring AOP中如何使用,首先需要了解适配模式的工作原理,然后结合Spring AOP的具体实现来详细详细解析源码。 首先,适配模式,也就是Adapter Pattern,属于结构型设计…...
Python 库自制 Cross-correlation 算法
Python 库自制 Cross-correlation 算法 引言正文引言 虽然 Scipy 库中包含了成熟的 Cross-correlation 算法,但是有些时候我们无法使用现成的库进行数据处理。这里介绍如何使用 Python 基础函数自制 Cross-correlation 算法。后续读者可以将该算法转换为其他各类语言。 正文…...
C++(23):为类成员函数增加this参数
C23允许指定类成员函数的第一个参数的this类型,从而更加便于函数重载: #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,引言2,安装Ollama工具3,下载DeepSeek R1 模型4,DeepSeek命令行对话5,DeepSeek API接口调用6,DeepSeek结合Web-ui实现图形化界面远程访问6.1&…...
【JAVA工程师从0开始学AI】,第四步:闭包与高阶函数——用Python的“魔法函数“重构Java思维
副标题:当严谨的Java遇上"七十二变"的Python函数式编程 历经变量战争、语法迷雾、函数对决,此刻我们将踏入Python最迷人的领域——函数式编程。当Java工程师还在用接口和匿名类实现回调时,Python的闭包已化身"智能机器人"…...
算法日记20:SC72最小生成树(prim朴素算法)
一、题目: 二、题解 2.1:朴素prim的步骤解析 O ( n 2 ) O(n^2) O(n2)(n<1e3) 0、假设,我们现在有这样一个有权图 1、我们随便找一个点,作为起点开始构建最小生成树(一般是1号),并且存入intree[]状态数组中…...
玩转SpringCloud Stream
背景及痛点 现如今消息中间件(MQ)在互联网项目中被广泛的应用,特别是大数据行业应用的特别的多,现在市面上也流行这多个消息中间件框架,比如ActiveMQ、RabbitMQ、RocketMQ、Kafka等,这些消息中间件各有各的优劣,但是想…...
嵌入式经常用到串口,如何判断串口数据接收完成?
说起通信,首先想到的肯定是串口,日常中232和485的使用比比皆是,数据的发送、接收是串口通信最基础的内容。这篇文章主要讨论串口接收数据的断帧操作。 空闲中断断帧 一些mcu(如:stm32f103)在出厂时就已经在…...
iOS App的启动与优化
App的启动流程 App启动分为冷启动和热启动 冷启动:从0开始启动App热启动:App已经在内存中,但是后台还挂着,再次点击图标启动App。 一般对App启动的优化都是针对冷启动。 App冷启动可分为三个阶段: dyld:…...
导出指定文件夹下的文件结构 工具模块-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. 按对角线进行矩阵排序 题目链接 本题可以暴力枚举,在确定了每一个对角线的第一个元素…...
【pytest】编写自动化测试用例命名规范README
API_autoTest 项目介绍 1. pytest命名规范 测试文件: 文件名需要以 test_ 开头或者以 _test.py 结尾。例如,test_login.py、user_management_test.py 这样的命名方式,pytest 能够自动识别并将其作为测试文件来执行其中的测试用例。 测试类…...
Compose常用UI组件
Compose常用UI组件 概述Modifier 修饰符常用Modifier修饰符作用域限定Modifier Modifier 实现原理Modifier.Element链的构建链的解析 常用基础组件常用布局组件列表组件 概述 Compose 预置了很多基础组件,如 Button,TextField,TopAppBar等&a…...
斐波那契数列模型:在动态规划的丝绸之路上追寻斐波那契的足迹(上)
文章目录 引言递归与动态规划的对比递归解法的初探动态规划的优雅与高效自顶向下的记忆化搜索自底向上的迭代法 性能分析与比较小结 引言 斐波那契数列,这一数列如同一条无形的丝线,穿越千年时光,悄然延续其魅力。其定义简单而优美ÿ…...
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 返回到前端修改代码:测试࿱…...
rustdesk编译修改名字
最近,我用Rust重写了一个2W行C代码的linux内核模块。在此记录一点经验。我此前没写过内核模块,认识比较疏浅,有错误欢迎指正。 为什么要重写? 这个模块2W行代码量看起来不多,却在线上时常故障,永远改不完。…...
BS5852英国家具防火安全条款主要包括哪几个方面呢?
什么是BS5852检测? BS5852是英国针对家用家具的强制性安全要求,主要测试家具在受到燃烧香烟和火柴等火源时的可燃性。这个标准通常分为四个部分进行测试,但实际应用中主要测试第一部分和第二部分,包括烟头测试和利用乙炔火焰模拟…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
Xcode 16 集成 cocoapods 报错
基于 Xcode 16 新建工程项目,集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...
