Solution: A Queue of Burst Times

Let’s start with the return value of the method. We need to return an array of completion times:

public static int[] completionTimes(int[] burstTimes, int quantum) {
  int n = burstTimes.length;
  int[] completion = new int[n];
  // Your implementation goes here
  return completion;
}

The problem statement already tells us the data structure: the line that tasks wait in is a queue. The plan is to simulate what the CPU does. Put all the tasks in the queue, and then repeat until the queue is empty: take the task at the front, run it for a slice of time, and either record its completion time or send it to the back of the line.

Even though we know the queue is the right data structure, there are still design choices to make. For example, what exactly goes in the queue? The tasks have burst times (and an order in the input array), so let’s start with the burst times and see whether that is enough. We can enqueue the burst times themselves:

Queue<Integer> line = new LinkedQueue<>();
for (int burst : burstTimes) {
  line.enqueue(burst);
}

With our running example, burstTimes = [9, 2, 7], the queue now holds the three burst times in input order:

┌───┬───┬───┐
│ 9 │ 2 │ 7 │
└───┴───┴───┘
  ▲       ▲
front    back

Now we want to simulate the CPU. We will need a loop that runs until the queue is empty:

while (!line.isEmpty()) {
  // run the task at the front of the line
}

We pick the task at the front of the line with line.front(), and then we need to run it for a slice of time. The slice is a full quantum, or the task’s remaining burst time, whichever is smaller, so Math.min(quantum, burst) gives us how much time to run it for:

while (!line.isEmpty()) {
  int burst = line.front();
  line.dequeue();
  int run = Math.min(quantum, burst);
  // run the task for 'run' units of time
}

After running the task, if its remaining burst time is 0, we record its completion time; if not, we send it to the back of the line. Let’s focus on recording the completion time first, because it shows we need more variables:

• We need to keep track of how much time has passed so far, which starts at 0 and increases as we run tasks.
• We need to know which task we are running, so we can record its completion time at the correct index of the completion array.

int time = 0;       // the current time
int taskIndex = 0;  // the task we are running
while (!line.isEmpty()) {
  int burst = line.front();
  line.dequeue();
  int run = Math.min(quantum, burst);
  time += run;   // increase the current time by the amount we ran
  burst -= run;  // decrease the burst time by the amount we ran
  if (burst == 0) {
    completion[taskIndex] = time;  // record the finish time
  } else {
    line.enqueue(burst);  // the remaining burst time goes to the back of the line
  }
}

Let’s focus on the taskIndex. I declared it, but still need to figure out how to update it. Let’s trace our running example. On the first turn of the loop, the 9 at the front runs for a quantum of 4, and its remaining burst time, 5, goes to the back of the line:

┌───┬───┬───┐
│ 2 │ 7 │ 5 │
└───┴───┴───┘
  ▲       ▲
front   back

We know which task each value belongs to because we just traced the first turn:

• The 2 at the front belongs to the second task (index 1).
• The 7 in the middle belongs to the third task (index 2).
• The 5 at the back belongs to the first task (index 0).

But this information is not recorded in the queue or anywhere else. As we loop through the tasks, we lose track of which task each burst time belongs to, especially when some tasks end and never return to the queue.

That makes it difficult to update taskIndex correctly.