[LeetCode][1834. Single-Threaded CPU] How to Maintain the Enqueued Tasks? | Sorting the array then Priority Queue | minHeap

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 3.5k 阅读时长 ≈ 3 分钟

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}\).

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

  2. 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
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 \(\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
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(n \log n)\).
  • 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. 😉😃💗