Leetcode 1834. Single-Threaded CPU Solution
Problem Description:
In this problem, we are given n
tasks represented by a 2D integer array tasks
, where tasks[i] = [enqueueTimei, processingTimei]
. This means that the i-th
task will be available for processing at enqueueTimei
and will take processingTimei
to finish. We have a single-threaded CPU that can process at most one task at a time, and it follows the below rules:
- If the CPU is idle and there are no available tasks to process, the CPU remains idle.
- If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
- Once a task is started, the CPU will process the entire task without stopping.
- The CPU can finish a task then start a new one instantly.
We need to return the order in which the CPU will process the tasks.
Walkthrough
Suppose we have input tasks: [[1, 2], [2, 4], [3, 2], [4, 1]]
. Let's walk through the algorithm step by step.
- Sort the tasks by their
enqueueTime
. Our tasks array becomes[[1, 2, 0], [2, 4, 1], [3, 2, 2], [4, 1, 3]]
, where the third element in each subarray is the task's original index. - Initialize an empty priority queue
minHeap
which sorts tasks byprocessingTime
. Then initialize variablesi = 0
(task pointer) andtime = 0
(current time). - Start processing tasks:
- As
minHeap
is empty, we set thetime
to the first task'senqueueTime
(1). - Now, we loop through the tasks and add all tasks whose
enqueueTime
is less than or equal totime
intominHeap
. In our example, task 0 and task 1 both meet this condition and are added tominHeap
. - Pop the task with the smallest
processingTime
fromminHeap
, and process it completely. Update the CPU's time accordingly. In our case, task 0 is popped and processed, making CPU'stime
equal to 3. - Add tasks into
minHeap
again, which have anenqueueTime
less than or equal to the updatedtime
. In our case, task 2 is added. - Again, process the task with the smallest
processingTime
fromminHeap
. Task 2 is processed, and the CPU'stime
becomes 5. - Add tasks into
minHeap
again. Task 3 is added. - Process task 3, making time 6.
- Process task 1, making time 10.
- As
- With no more tasks in
minHeap
, our final order is[0, 2, 3, 1]
.
Solution
C++
1#include <vector>
2#include <queue>
3#include <algorithm>
4#include <utility>
5
6using namespace std;
7
8class Solution {
9 public:
10 vector<int> getOrder(vector<vector<int>>& tasks) {
11 int n = tasks.size();
12
13 // Add index information.
14 for (int i = 0; i < n; ++i)
15 tasks[i].push_back(i);
16
17 // Sort tasks by their enqueueTime.
18 sort(tasks.begin(), tasks.end());
19
20 vector<int> ans;
21 // Create a minHeap that sorts tasks by processingTime.
22 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
23 int i = 0; // Task pointer
24 long time = 0; // Current time
25
26 while (i < n || !minHeap.empty()) {
27 if (minHeap.empty())
28 time = max(time, static_cast<long>(tasks[i][0]));
29
30 // Add all tasks with enqueueTime <= time to minHeap
31 while (i < n && time >= tasks[i][0]) {
32 minHeap.emplace(tasks[i][1], tasks[i][2]);
33 ++i;
34 }
35
36 // Process the task with the smallest processingTime from minHeap
37 const auto [procTime, index] = minHeap.top();
38 minHeap.pop();
39 time += procTime;
40 ans.push_back(index);
41 }
42
43 return ans;
44 }
45};
Python
1from typing import List
2import heapq
3
4class Solution:
5 def getOrder(self, tasks: List[List[int]]) -> List[int]:
6 n = len(tasks)
7
8 # Add index information.
9 for i in range(n):
10 tasks[i].append(i)
11
12 # Sort tasks by their enqueueTime.
13 tasks.sort()
14
15 ans = []
16 # Create a minHeap that sorts tasks by processingTime.
17 min_heap = []
18 i = 0 # Task pointer
19 time = 0 # Current time
20
21 while i < n or min_heap:
22 if not min_heap:
23 time = max(time, tasks[i][0])
24
25 # Add all tasks with enqueueTime <= time to min_heap
26 while i < n and time >= tasks[i][0]:
27 heapq.heappush(min_heap, (tasks[i][1], tasks[i][2]))
28 i += 1
29
30 # Process the task with the smallest processingTime from min_heap
31 proc_time, index = heapq.heappop(min_heap)
32 time += proc_time
33 ans.append(index)
34
35 return ans
JavaScript
1class PriorityQueue {
2 constructor() {
3 this.queue = [];
4 }
5
6 push(value) {
7 let i = this.queue.findIndex(([p, idx]) => p > value[0] || (p === value[0] && idx > value[1]));
8 if (i === -1) {
9 this.queue.push(value);
10 } else {
11 this.queue.splice(i, 0, value);
12 }
13 }
14
15 pop() {
16 return this.queue.shift();
17 }
18
19 empty() {
20 return this.queue.length === 0;
21 }
22}
23
24function getOrder(tasks) {
25 const n = tasks.length;
26
27 // Add index information.
28 tasks.forEach((task, idx) => task.push(idx));
29
30 // Sort tasks by their enqueueTime.
31 tasks.sort((a, b) => a[0] - b[0]);
32
33 const ans = [];
34 // Create a minHeap that sorts tasks by processingTime.
35 const minHeap = new PriorityQueue();
36 let i = 0; // Task pointer
37 let time = 0; // Current time
38
39 while (i < n || !minHeap.empty()) {
40 if (minHeap.empty())
41 time = Math.max(time, tasks[i][0]);
42
43 // Add all tasks with enqueueTime <= time to minHeap
44 while (i < n && time >= tasks[i][0]) {
45 minHeap.push([tasks[i][1], tasks[i][2]]);
46 i += 1;
47 }
48
49 // Process the task with the smallest processingTime from minHeap
50 const [procTime, index] = minHeap.pop();
51 time += procTime;
52 ans.push(index);
53 }
54
55 return ans;
56}