[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 33 questions:

  1. Which task should int the enqueued tasks list?

  2. How to maintain the enqueued tasks?

  3. Which task of the enqueued tasks should the CPU choose?

Let’s answer the 33 questions:

  1. We assign the tasks to the CPU by enqueueTime\textit{enqueueTime}, so we sort the array first by enqueueTime\textit{enqueueTime}. However, we will lose the index\textit{index} of the task.

We can parse the task by creating a new class Job\texttt{Job}, whose members are id\textit{id}, enqueueTime\textit{enqueueTime}, processTime\textit{processTime}.

  1. We put all the tasks assigned to the CPU into a Priority Queue and poll out the task whose processTime\textit{processTime} is the least each time.

  2. We can maintain a curTime\textit{curTime} variable, which represents the current time with initial value is 00.

If the CPU has no tasks to execute, we set the curTime\textit{curTime} to enqueueTime\textit{enqueueTime} of the next task in the array that has not yet been assigned to the CPU.

After this, we put all enqueueTimecurTime\textit{enqueueTime} \le \textit{curTime} tasks into the Priority Queue.

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
// Priority Queue time: O(nlogn) space: O(n)
public int[] getOrder(int[][] tasks) {
int len = tasks.length;

Job[] jobs = new Job[len];
for (int i = 0; i < len; i++) {
jobs[i] = new Job(i, tasks[i][0], tasks[i][1]);
}

Arrays.sort(jobs, (job1, job2) -> {
if (job1.enqueueTime == job2.enqueueTime) {
return job1.processTime - job2.processTime;
}

return job1.enqueueTime - job2.enqueueTime;
});

PriorityQueue<Job> pq = new PriorityQueue<>((job1, job2) -> {
if (job1.processTime == job2.processTime) {
return job1.id - job2.id;
}

return job1.processTime - job2.processTime;
});

int[] ans = new int[len];
int idIdx = 0;
int jobIdx = 0;
int curTime = 0;

while (jobIdx < len) {
if (pq.isEmpty()) {
curTime = Math.max(curTime, jobs[jobIdx].enqueueTime);
}

while (jobIdx < len && jobs[jobIdx].enqueueTime <= curTime) {
pq.offer(jobs[jobIdx]);
jobIdx++;
}

Job job = pq.poll();
ans[idIdx++] = job.id;
curTime += job.processTime;
}

while (!pq.isEmpty()) {
ans[idIdx++] = pq.poll().id;
}

return ans;
}

class Job {
int id;
int enqueueTime;
int processTime;

Job(int id, int enqueueTime, int processTime) {
this.id = id;
this.enqueueTime = enqueueTime;
this.processTime = processTime;
}
}
}

We can use an extra array which store the indices of the tasks\textit{tasks}, then sorting the array by enqueueTime\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
41
class 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)O(nlogn).
  • Space Complexity: O(n)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. 😉😃💗