LeetCode 题解工作台
单线程 CPU
给你一个二维数组 tasks ，用于表示 n 项从 0 到 n - 1 编号的任务。其中 tasks[i] = [enqueueTime i , processingTime i ] 意味着第 i 项任务将会于 enqueueTime i 时进入任务队列，需要 …
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数组·排序
答案摘要
我们先将任务按照 `enqueueTime` 从小到大排序，接下来用一个优先队列（小根堆）维护当前可执行的任务，队列中的元素为 `(processingTime, index)`，即任务的执行时间和任务的编号。另外用一个变量 表示当前时间，初始值为 。 接下来我们模拟任务的执行过程。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·排序 题型思路
题目描述
给你一个二维数组 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 == n1 <= n <= 1051 <= enqueueTimei, processingTimei <= 109
解题思路
方法一：排序 + 优先队列（小根堆）
我们先将任务按照 enqueueTime 从小到大排序，接下来用一个优先队列（小根堆）维护当前可执行的任务，队列中的元素为 (processingTime, index)，即任务的执行时间和任务的编号。另外用一个变量 表示当前时间，初始值为 。
接下来我们模拟任务的执行过程。
如果当前队列为空，说明当前没有可执行的任务，我们将 更新为下一个任务的 enqueueTime 与当前时间 中的较大值。接下来将所有 enqueueTime 小于等于 的任务加入队列。
然后从队列中取出一个任务，将其编号加入答案数组，然后将 更新为当前时间 与当前任务的执行时间之和。
循环上述过程，直到队列为空，且所有任务都已经加入过队列。
时间复杂度 ，其中 为任务的数量。
class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
for i, task in enumerate(tasks):
task.append(i)
tasks.sort()
ans = []
q = []
n = len(tasks)
i = t = 0
while q or i < n:
if not q:
t = max(t, tasks[i][0])
while i < n and tasks[i][0] <= t:
heappush(q, (tasks[i][1], tasks[i][2]))
i += 1
pt, j = heappop(q)
ans.append(j)
t += pt
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's understanding of sorting and heap usage for task prioritization.
- question_mark
Watch for the candidate's ability to efficiently simulate the process while managing available tasks.
- question_mark
Check if the candidate efficiently handles edge cases like tasks arriving at the same time.
常见陷阱
外企场景- error
Not handling idle CPU situations properly when there are no tasks to process.
- error
Forgetting to prioritize the shortest task when multiple tasks are available.
- error
Overcomplicating the task management instead of leveraging sorting and heap efficiently.
进阶变体
外企场景- arrow_right_alt
Modify the problem to handle a multi-threaded CPU with more than one task running simultaneously.
- arrow_right_alt
Change the tasks' characteristics to involve different priority schemes (e.g., prioritize by processing time or enqueue time).
- arrow_right_alt
Introduce task dependencies where some tasks cannot be started until others are completed.