算法:外卖调度
题目
有N个餐厅和M个外卖员,每个餐厅在某个时间点会产生一个外卖订单,这些订单都有产生时间、所需送达时间和优先级。外卖员在空闲时会选择最优先的订单来配送,直到所有订单都被送达。具体规则如下: 对于每个餐厅的订单,优先级高的订单优先,其次是所需送达时间最短的订单,再次是产生时间最早的订单。外卖员在空闲时会从所有餐厅的最高优先级订单中挑选一个所需送达时间最短的订单进行配送,若所需送达时间相同则选择餐厅编号最小的订单。
输入描述
第一行三个数N、M、P,分别表示有N个餐厅,M个外卖员,P个订单随后有P行,每行有4个数字,分别是餐厅编号、产生时间、优先级和所需送达时间。
输出描述
输出P行,每行表示每个订单被送达的时间点。
示例:
输入:
2 2 4
1 1 2 5
1 4 3 2
2 2 1 4
2 5 2 1
输出:
6
8
6
7
实现思路
-
订单的排序与优先队列:
- 首先将所有订单按照产生时间进行排序。这样可以按照时间顺序逐步处理订单。
- 使用一个优先队列
pq
(最大堆)来存储当前时间点可以处理的订单,并根据优先级、送达时间、餐厅编号的规则排序。
-
外卖员的空闲时间管理:
- 使用一个最小堆
delivery_boys
来记录每个外卖员的空闲时间。最小堆确保我们总是优先分配订单给最早空闲的外卖员。
- 使用一个最小堆
-
模拟订单分配:
- 当前时间点为最早空闲的外卖员的空闲时间或者下一个订单的产生时间。
- 将当前时间点之前产生的所有订单加入优先队列
pq
中。 - 从
pq
中选择最优的订单,分配给最早空闲的外卖员,并更新外卖员的空闲时间。 - 如果
pq
中没有订单,时间推进到下一个订单产生的时间。
-
更新订单送达时间:
- 外卖员选择订单后,送达时间为外卖员当前空闲时间或订单产生时间(取两者较大值)加上订单的送达时间。
- 记录每个订单的送达时间,并将外卖员的空闲时间更新为新的送达时间。
C++ 代码
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>using namespace std;struct Order {int restaurant;int start_time;int priority;int delivery_time;int index; // 记录订单的原始顺序
};// 定义优先级队列的排序规则
struct Compare {bool operator()(Order const& a, Order const& b) {if (a.priority != b.priority) return a.priority < b.priority;if (a.delivery_time != b.delivery_time) return a.delivery_time > b.delivery_time;return a.restaurant > b.restaurant;}
};int main() {int N = 2, M = 2, P = 4;vector<Order> orders(P);orders[0] = {1,1,2,5,0};orders[1] = {1,4,3,2,1};orders[2] = {2,2,1,4,2};orders[3] = {2,5,2,1,3};// 按产生时间排序sort(orders.begin(), orders.end(), [](Order const& a, Order const& b) {return a.start_time < b.start_time;});vector<int> result(P, 0);priority_queue<Order, vector<Order>, Compare> pq;// 外卖员的空闲时间,最小堆priority_queue<int, vector<int>, greater<int>> delivery_boys;// 初始化所有外卖员为空闲状态for (int i = 0; i < M; i++) {delivery_boys.push(0);}int i = 0;while (i < P || !pq.empty()) {// 当前时间为最早的外卖员空闲时间或下一个订单的产生时间int current_time = delivery_boys.top();if (i < P) {current_time = max(current_time, orders[i].start_time);}// 将当前时间之前产生的订单加入优先队列while (i < P && orders[i].start_time <= current_time) {pq.push(orders[i]);i++;}if (!pq.empty()) {// 取出最早空闲的外卖员int delivery_boy_time = delivery_boys.top();delivery_boys.pop();// 选择优先级最高的订单Order top_order = pq.top();pq.pop();// 更新订单送达时间int delivery_time = max(delivery_boy_time, top_order.start_time) + top_order.delivery_time;result[top_order.index] = delivery_time;// 更新外卖员的空闲时间delivery_boys.push(delivery_time);} else {// 如果当前没有订单可分配,推进时间到下一个订单的产生时间if (i < P) {delivery_boys.push(orders[i].start_time);}}}for (int i = 0; i < P; i++) {cout << result[i] << endl;}return 0;
}
时间复杂度
-
初始排序:
- 将订单按产生时间排序的时间复杂度为 O(PlogP)O(P \log P)O(PlogP),其中 PPP 是订单数量。
-
模拟分配过程:
- 每个订单最多进入和弹出优先队列一次,进入优先队列的时间复杂度为 O(logP)O(\log P)O(logP)。
- 外卖员的空闲时间最小堆操作(插入和弹出)的时间复杂度为 O(logM)O(\log M)O(logM),其中 MMM 是外卖员的数量。
- 总的模拟分配过程的时间复杂度为 O(PlogP+PlogM)O(P \log P + P \log M)O(PlogP+PlogM)。
综合考虑,时间复杂度为 O(PlogP+PlogM)O(P \log P + P \log M)O(PlogP+PlogM)。
空间复杂度
-
优先队列
pq
和delivery_boys
:- 优先队列
pq
最多存储 PPP 个订单,因此空间复杂度为 O(P)O(P)O(P)。 - 最小堆
delivery_boys
始终存储 MMM 个外卖员的空闲时间,因此空间复杂度为 O(M)O(M)O(M)。
- 优先队列
-
其他存储:
orders
数组存储 PPP 个订单的信息,因此空间复杂度为 O(P)O(P)O(P)。result
数组存储每个订单的送达时间,因此空间复杂度为 O(P)O(P)O(P)。
综合考虑,空间复杂度为 O(P+M)O(P + M)O(P+M)。
相关文章:
算法:外卖调度
题目 有N个餐厅和M个外卖员,每个餐厅在某个时间点会产生一个外卖订单,这些订单都有产生时间、所需送达时间和优先级。外卖员在空闲时会选择最优先的订单来配送,直到所有订单都被送达。具体规则如下: 对于每个餐厅的订单,优先级高…...

leetcode50. Pow(x, n),快速幂算法
leetcode50. Pow(x, n),快速幂算法 实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。 示例 1: 输入:x 2.00000, n 10 输出:1024.00000 示例 2: 输入ÿ…...

Xinstall神器来袭,轻松搞定CPA推广渠道统计!
在数字化营销日益盛行的今天,CPA(按行动付费)推广已成为众多企业营销的重要手段。然而,随着渠道流量和获客途径的不断变化,CPA推广渠道统计的痛点也日益凸显。别担心,Xinstall来帮你解决问题! …...
011 | efinance分析豆一主连期货
👉👉👉 《玩转Python金融量化专栏》👈👈👈 订阅本专栏的可以下载对应的代码和数据集 🚀 上一篇🌟 下一篇⬅️ 010 东方财富帖子标题情绪分析012 akshare分析NYBOT棉花历史数据 ➡️豆一主连期货(通常简称“豆一”)是指中国期货市场上以大豆为标的的期货合约…...

【Python】函数入门(下)
3))* ** 注意:也遵循位置传参在前面,按关键字传参在后面。 代码示例: def func(*args,**kwargs):print(args,kwargs) 该函数中的参数会自动根据传参的方式不同(即:按位置…...
git的基本概念和使用原理
Git是一个分布式版本控制系统,用于跟踪文件的更改并协调多个开发人员之间的工作。以下是Git的基本概念和使用原理及方式: 目录 基本概念 使用原理 基本操作示例 基本概念 版本库(Repository): 版本库是Git用来保存…...

手写简化版的vue-router
vue-router作为vue全家桶之一的重要插件,有必要去深究一下,今天我们就从0到1手写一个简化版本。 开始之前,我们使用路由插件时是先进行下载路由 npm i vue-router ,然后在main.js中使用app.use导入router插件。想要手写vue-rou…...

分享一个基于uni-app的蛋糕商城订购小程序的设计与实现(源码、调试、LW、开题、PPT)
💕💕作者:计算机源码社 💕💕个人简介:本人 八年开发经验,擅长Java、Python、PHP、.NET、Node.js、Android、微信小程序、爬虫、大数据、机器学习等,大家有这一块的问题可以一起交流&…...

Python绘图入门:使用Matplotlib绘制柱状图
Python绘图入门:使用Matplotlib绘制柱状图 柱状图是一种常见的数据可视化方式,能够直观地展示不同类别之间的数据差异。在Python中,Matplotlib是一个非常强大且灵活的绘图库,它不仅能绘制简单的图表,还能创建复杂的多…...

Qt5编译qmqtt库使用MQTT协议连接华为云IOT完成数据上传与交互
一、前言 随着物联网技术的发展,越来越多的设备通过网络互相连接,形成了庞大的智能系统。这些系统能够收集、分析并响应各种数据,从而实现自动化控制和智能化管理。在这个背景下,MQTT 成为了一个广泛使用的轻量级消息传输协议,特别适用于资源受限的环境,如移动应用或远程…...

mysql速起架子
wget https://dev.mysql.com/get/Downloads/MySQL-8.0/mysql-8.0.21-linux-glibc2.12-x86_64.tar.xz 下载mysql tar xvJf mysql-8.0.21-linux-glibc2.12-x86_64.tar.xz 解压 mv mysql-8.0.21-linux-glibc2.12-x86_64 mysql-8.0 改名 去到bin目录 cd bin mkdir data gr…...

云动态摘要 2024-08-14
给您带来云厂商的最新动态,最新产品资讯和最新优惠更新。 最新优惠与活动 注册阿里云免费领云服务器_云服务器ECS_阿里云 阿里云 2024-08-14 云上试用新玩法,个人享300元免费额度,企业享660元免费额度,多种规格随心试 [免费体验…...
Elasticsearch 桶(Bucket)聚合详解及示例
在 Elasticsearch 中,桶(Bucket)聚合是一种强大的工具,它允许我们对数据进行分组并统计每组的数量。这种聚合类型对于理解数据的分布和进行分组统计非常有用。本文将详细介绍 Elasticsearch 的桶聚合,并提供完整的示例…...

Django基础知识
文章目录 新建Django项目helloworld关联数据库admin 新建Django项目 创建django-admin startproject project_name 运行 python manage.py runserver 创建app: python manage.py startapp app_name 目录: 配置文件 settings.py 路由配置 urls.py 项目管理 manage.p…...

使用 nginx 搭建代理服务器(正向代理 https 网站)指南
简介 正向代理 简介 在企业开发环境中,局域网内的设备通常需要通过正向代理服务器访问互联网。正向代理服务器充当中介,帮助客户端请求外部资源并返回结果。局域网内也就是俗称的内网,局域网外的互联网就是外网,在一些特殊场景内…...

深入解析亚马逊数据采集工具选择:Data API/Scrape API/Pangolin采集器
引言 在当今电商领域,亚马逊已成为全球最大的在线零售平台之一。随着竞争的加剧和市场的多样化,商家和企业不仅需要优秀的产品和服务,还需要通过深入的数据分析来制定更加精准的市场策略。因此,采集亚马逊站点数据已成为企业实现…...
探索Linux多样性:主流发行版及其应用场景
目录 引言 Debian:稳定性的标杆 Ubuntu:易用性的代表 Red Hat Enterprise Linux (RHEL):企业的首选 Fedora:创新的前沿 CentOS:开源的稳定之选 Arch Linux:高级用户的定制天堂 Gentoo:性…...

CentOS7.6 HAproxy-7层负载均衡集群——实施方案
目录 1、前期环境准备 1.准备4台主机 1. 设置主机名 2. 设置IP地址然后重启网卡 3. 关闭防火墙和selinux 4. 全部的服务器完成时间统一 二、配置haproxy(192.168.200.11)服务器 1. 安装haproxy 2. haproxy 配置中分成五部分内容 3. 配置HAproxy(192.168.2…...
升级ubuntu22.10到24.04
将所有kinetic换成noble,noble是24.04源,sed或手动改。 cd /etc/aptgrep -nr kinetic将old-releases.ubuntu.com替换成国内的地址,因为2210国内源没找到,没有了,但是现在更新到24.04,国内是有的。 apt up…...

YOLO好像也没那么难?
“学YOLO的念头是想整个游戏外挂!” 目录 基本原理 模型推理 IOU交并比 NMS非极大值抑制 模型训练 损失函数LOSS 代码实现 YOLO学习渠道 基本原理 模型推理 学习一个新的神经网络结构,作者认为整明白输入和输出是怎么回事就OK了,至于…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...

2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...
CppCon 2015 学习:REFLECTION TECHNIQUES IN C++
关于 Reflection(反射) 这个概念,总结一下: Reflection(反射)是什么? 反射是对类型的自我检查能力(Introspection) 可以查看类的成员变量、成员函数等信息。反射允许枚…...