[LeetCode][1834. Single-Threaded CPU] How to Maintain the Enqueued Tasks? | Sorting the array then Priority Queue | minHeap
By Long Luo
This article is the solution How to Maintain the Enqueued Tasks? | Sorting the array then Priority Queue | minHeap of Problem 1834. Single-Threaded CPU.
Intuition
To simulate the CPU operations, there comes \(3\) questions:
Which task should int the enqueued tasks list?
How to maintain the enqueued tasks?
Which task of the enqueued tasks should the CPU choose?
Let’s answer the \(3\) questions:
- We assign the tasks to the CPU by \(\textit{enqueueTime}\), so we sort the array first by \(\textit{enqueueTime}\). However, we will lose the \(\textit{index}\) of the task.
We can parse the task by creating a new class \(\texttt{Job}\), whose members are \(\textit{id}\), \(\textit{enqueueTime}\), \(\textit{processTime}\).
We put all the tasks assigned to the CPU into a Priority Queue and poll out the task whose \(\textit{processTime}\) is the least each time.
We can maintain a \(\textit{curTime}\) variable, which represents the current time with initial value is \(0\).
If the CPU has no tasks to execute, we set the \(\textit{curTime}\) to \(\textit{enqueueTime}\) of the next task in the array that has not yet been assigned to the CPU.
After this, we put all \(\textit{enqueueTime} \le \textit{curTime}\) tasks into the Priority Queue.
1 | class Solution { |
We can use an extra array which store the indices of the \(\textit{tasks}\), then sorting the array by \(\textit{enqueueTime}\).
So we can write more clean code.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
41class Solution {
public int[] getOrder(int[][] tasks) {
int len = tasks.length;
Integer[] indices = new Integer[len];
for (int i = 0; i < len; i++) {
indices[i] = i;
}
Arrays.sort(indices, Comparator.comparingInt(idx -> tasks[idx][0]));
PriorityQueue<int[]> pq = new PriorityQueue<>((task1, task2) -> {
if (task1[1] == task2[1]) {
return task1[0] - task2[0];
}
return task1[1] - task2[1];
});
int[] ans = new int[len];
int time = 0;
int k = 0;
for (int i = 0; i < len; i++) {
if (pq.isEmpty()) {
time = Math.max(time, tasks[indices[k]][0]);
}
while (k < len && tasks[indices[k]][0] <= time) {
pq.offer(new int[]{indices[k], tasks[indices[k]][1]});
k++;
}
int[] curr = pq.poll();
time += curr[1];
ans[i] = curr[0];
}
return ans;
}
}
Analysis
- Time Complexity: \(O(nlogn)\).
- Space Complexity: \(O(n)\).
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗