1834-单线程 CPU

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给你一个二维数组 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 <= 105
  • 1 <= enqueueTimei, processingTimei <= 109

方法一：排序 + 优先队列

提示 1

我们需要两个数据结构来实现题目描述中的 CPU 操作。

  • 第一个数据结构负责按照时间顺序将任务分配给 CPU；
  • 第二个数据结构负责帮助 CPU 在所有任务中选择处理时间最小的那个执行。

你能想出这两个数据结构分别是什么吗？

思路与算法

第一个数据结构即为数组。我们将数组 task 中的所有任务按照 enqueueTime}_i 升序排序即可。

需要注意的是，在排序完成之后，我们就会丢失任务的编号信息。一种可行的解决方案是，我们使用一个长度为 n 的数组存储编号，并直接对编号进行自定义排序，排序的标准即为 enqueueTime}_i。

第二个数据结构即为优先队列（小根堆）。我们将所有分配给 CPU 的任务放入优先队列中，每次取出处理时间 processingTime}_i 最小的任务执行。

细节

为了使得上面的两个数据结构能够帮助我们解决本题，我们可以维护一个时间戳变量 timestamp，表示当前的时间，它的初始值为 0。

我们需要让 CPU 执行所有的 n 个任务，在执行第 i 个任务前：

  • 如果 CPU 没有可以执行的任务（即优先队列为空），我们将时间戳直接「快进」到数组中下一个还没有分配给 CPU 的那个任务的 enqueueTime}_i；

  • 在这之后，我们将所有 enqueueTime}_i \leq \textit{timestamp 的任务放入优先队列中。我们可以使用一个指针在数组上从前往后进行遍历，保证每个任务只会被加入优先队列恰好一次；

  • 最终我们就可以在优先队列中挑选 processingTime}_i 最小的那个任务让 CPU 来执行，并且我们需要将 timestamp 增加 processingTime}_i。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
private:
    using PII = pair<int, int>;
    using LL = long long;

public:
    vector<int> getOrder(vector<vector<int>>& tasks) {
        int n = tasks.size();
        vector<int> indices(n);
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(), [&](int i, int j) {
            return tasks[i][0] < tasks[j][0];
        });

        vector<int> ans;
        // 优先队列
        priority_queue<PII, vector<PII>, greater<PII>> q;
        // 时间戳
        LL timestamp = 0;
        // 数组上遍历的指针
        int ptr = 0;
        
        for (int i = 0; i < n; ++i) {
            // 如果没有可以执行的任务，直接快进
            if (q.empty()) {
                timestamp = max(timestamp, (LL)tasks[indices[ptr]][0]);
            }
            // 将所有小于等于时间戳的任务放入优先队列
            while (ptr < n && tasks[indices[ptr]][0] <= timestamp) {
                q.emplace(tasks[indices[ptr]][1], indices[ptr]);
                ++ptr;
            }
            // 选择处理时间最小的任务
            auto&& [process, index] = q.top();
            timestamp += process;
            ans.push_back(index);
            q.pop();
        }
        
        return ans;
    }
};

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        n = len(tasks)
        indices = list(range(n))
        indices.sort(key=lambda x: tasks[x][0])

        ans = list()
        # 优先队列
        q = list()
        # 时间戳
        timestamp = 0
        # 数组上遍历的指针
        ptr = 0
        
        for i in range(n):
            # 如果没有可以执行的任务，直接快进
            if not q:
                timestamp = max(timestamp, tasks[indices[ptr]][0])
            # 将所有小于等于时间戳的任务放入优先队列
            while ptr < n and tasks[indices[ptr]][0] <= timestamp:
                heapq.heappush(q, (tasks[indices[ptr]][1], indices[ptr]))
                ptr += 1
            # 选择处理时间最小的任务
            process, index = heapq.heappop(q)
            timestamp += process
            ans.append(index)
        
        return ans

复杂度分析

  • 时间复杂度：O(n \log n)。排序的时间复杂度为 O(n \log n)，优先队列单次操作的时间复杂度为 O(\log n)，操作的次数为 O(n)。

  • 空间复杂度：O(n)，即为存储编号的数组以及优先队列需要使用的空间。

 Comments
On this page
1834-单线程 CPU