【算法题】1834. 单线程 CPU
创始人
2024-05-28 21:58:13
0

插: 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。
坚持不懈,越努力越幸运,大家一起学习鸭~~~

题目:

给你一个二维数组 tasks ,用于表示 n 项从 0 到 n - 1 编号的任务。其中 tasks[i] = [enqueueTimei, processingTimei] 意味着第 i 项任务将会于 enqueueTimei 时进入任务队列,需要 processingTimei 的时长完成执行。

现有一个单线程 CPU ,同一时间只能执行 最多一项 任务,该 CPU 将会按照下述方式运行:

如果 CPU 空闲,且任务队列中没有需要执行的任务,则 CPU 保持空闲状态。
如果 CPU 空闲,但任务队列中有需要执行的任务,则 CPU 将会选择 执行时间最短 的任务开始执行。如果多个任务具有同样的最短执行时间,则选择下标最小的任务开始执行。
一旦某项任务开始执行,CPU 在 执行完整个任务 前都不会停止。
CPU 可以在完成一项任务后,立即开始执行一项新任务。
返回 CPU 处理任务的顺序。

示例 1:

输入:tasks = [[1,2],[2,4],[3,2],[4,1]]
输出:[0,2,3,1]
解释:事件按下述流程运行:

  • time = 1 ,任务 0 进入任务队列,可执行任务项 = {0}
  • 同样在 time = 1 ,空闲状态的 CPU 开始执行任务 0 ,可执行任务项 = {}
  • time = 2 ,任务 1 进入任务队列,可执行任务项 = {1}
  • time = 3 ,任务 2 进入任务队列,可执行任务项 = {1, 2}
  • 同样在 time = 3 ,CPU 完成任务 0 并开始执行队列中用时最短的任务 2 ,可执行任务项 = {1}
  • time = 4 ,任务 3 进入任务队列,可执行任务项 = {1, 3}
  • time = 5 ,CPU 完成任务 2 并开始执行队列中用时最短的任务 3 ,可执行任务项 = {1}
  • time = 6 ,CPU 完成任务 3 并开始执行任务 1 ,可执行任务项 = {}
  • time = 10 ,CPU 完成任务 1 并进入空闲状态
    示例 2:

输入:tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
输出:[4,3,2,0,1]
解释:事件按下述流程运行:

  • time = 7 ,所有任务同时进入任务队列,可执行任务项 = {0,1,2,3,4}
  • 同样在 time = 7 ,空闲状态的 CPU 开始执行任务 4 ,可执行任务项 = {0,1,2,3}
  • time = 9 ,CPU 完成任务 4 并开始执行任务 3 ,可执行任务项 = {0,1,2}
  • time = 13 ,CPU 完成任务 3 并开始执行任务 2 ,可执行任务项 = {0,1}
  • time = 18 ,CPU 完成任务 2 并开始执行任务 0 ,可执行任务项 = {1}
  • time = 28 ,CPU 完成任务 0 并开始执行任务 1 ,可执行任务项 = {}
  • time = 40 ,CPU 完成任务 1 并进入空闲状态

提示:

tasks.length == n
1 <= n <= 10^5
1 <= enqueueTimei, processingTimei <= 10^9

java代码:

class Solution {public int[] getOrder(int[][] ts) {int n = ts.length;// 将 ts 转存成 nts,保留任务编号int[][] nts = new int[n][3];for (int i = 0; i < n; i++) nts[i] = new int[]{ts[i][0], ts[i][1], i};// 根据任务入队时间进行排序Arrays.sort(nts, (a,b)->a[0]-b[0]);// 根据题意,先按照「持续时间」排序,再根据「任务编号」排序PriorityQueue q = new PriorityQueue<>((a,b)->{if (a[1] != b[1]) return a[1] - b[1];return a[2] - b[2];});int[] ans = new int[n];for (int time = 1, j = 0, idx = 0; idx < n; ) {// 如果当前任务可以添加到「队列」中(满足入队时间)则进行入队while (j < n && nts[j][0] <= time) q.add(nts[j++]);if (q.isEmpty()) {// 如果当前「队列」没有任务,直接跳到下个任务的入队时间time = nts[j][0];} else {// 如果有可执行任务的话,根据优先级将任务出队(记录下标),并跳到该任务完成时间点int[] cur = q.poll();ans[idx++] = cur[2];time += cur[1];}}return ans;}
}

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播,要解决的几个问题是:1&...
Windows10添加群晖磁盘... 在使用群晖NAS时,我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章,在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
【PdgCntEditor】解... 一、问题背景 大部分的图书对应的PDF,目录中的页码并非PDF中直接索引的页码...
修复 爱普生 EPSON L4... L4151 L4153 L4156 L4158 L4163 L4165 L4166 L4168 L4...
Fluent中创建监测点 1 概述某些仿真问题,需要创建监测点,用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装(Wind... 前言:刚换了一台电脑,里面所有东西都需要重新配置,习惯了所...
MFC文件操作  MFC提供了一个文件操作的基类CFile,这个类提供了一个没有缓存的二进制格式的磁盘...