...
/Feature #15: Queue Reconstruction by Priority
Feature #15: Queue Reconstruction by Priority
Implement the "Queue Reconstruction by Priority" feature for our "Operating System" project.
We'll cover the following...
Description
A process queue contains the process priority. It also contains the number of processes ahead of a process in the queue that has a priority not less than its own. Suppose that the OS crashed and now we only have an array of processes, with each process at a random position in the array. In this feature, we’ll reconstruct the process queue from the information available to us.
Each element in the 2D array consists of a process’s priority and the number of processes with a higher or equal priority that are ahead of it in the queue. An entry [pi, ki] represents that a process with priority pi has ki other processes, with a priority of at least pi, ahead of it in the queue.
Our task is to reconstruct and return the process queue.
Let’s look at a few examples of this:
Solution
A process with a lower priority does not affect the placement of k processes with a higher priority. So, we will first insert the processes with a higher priority, into the output array. We will start by sorting the input array in descending order of process priority, and then in ascending order of the k-value. We will:
- Sort the processes by priority, in a descending order.
- Sort the processes with the same