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 enqueueTime, so we sort the array first by enqueueTime. However, we will lose the index of the task.
We can parse the task by creating a new class Job, whose members are id, enqueueTime, processTime.
-
We put all the tasks assigned to the CPU into a Priority Queue and poll out the task whose processTime is the least each time.
-
We can maintain a curTime variable, which represents the current time with initial value is 0.
If the CPU has no tasks to execute, we set the curTime to enqueueTime of the next task in the array that has not yet been assigned to the CPU.
After this, we put all enqueueTime≤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 { 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, then sorting the array by 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).
- 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. 😉😃💗