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

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 $3$ questions:

1. 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}$.

2. 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.

3. 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.

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 $\textit{tasks}$, then sorting the array by $\textit{enqueueTime}$.

So we can write more clean code.

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. 😉😃💗