Solution: A Queue of Task Indices

We still need a way to tell which task is at the front of the queue. One option is to write a class that represents a task, with two fields: the burst time and the task’s index in the input array. We would enqueue instances of that class. The two values would be stored together in the queue, so the front of the queue would tell us both the burst time and which task it belongs to.

That would work. But when a task reaches the front, what we actually need is its index, so we can update its burst time and eventually record its finish time in the output array at that same index. We already store the burst times in the burstTimes array and the finish times in the completion array, so the index lets us look up and update the task’s entry in both arrays. So the queue does not need the burst times at all. We enqueue the indices.

The burst times change as tasks run. So we need to update the values in the burstTimes array. This is not the best practice, because it modifies the input array. The caller may still need the input array. A better approach is to make a local copy of the burst times array and work with that copy instead. I am going to call this copy remaining because it keeps track of how much time is left for each task.

Let’s update the code from earlier and implement this idea:

public static int[] completionTimes(int[] burstTimes, int quantum) {
  int n = burstTimes.length;
  int[] remaining = new int[n];   // how much time is left for each task
  int[] completion = new int[n];  // the finish time of each task
  Queue<Integer> line = new LinkedQueue<>();  // the queue of task indices

  // initialize the remaining times and enqueue the task indices
  for (int i = 0; i < n; i++) {
    remaining[i] = burstTimes[i];  // initially, all of the burst time remains
    line.enqueue(i);
  }

  int time = 0;  // the current time
  while (!line.isEmpty()) {
    int taskIndex = line.front();
    line.dequeue();
    int run = Math.min(quantum, remaining[taskIndex]);  // a full slice, or whatever is left
    time += run;
    remaining[taskIndex] -= run;
    if (remaining[taskIndex] == 0) {
      completion[taskIndex] = time;  // the task is done; record when
    } else {
      line.enqueue(taskIndex);       // not done; back of the line
    }
  }
  return completion;
}

The loop is the same as our first attempt. The difference is that the values in the queue are now indices, and we use remaining[taskIndex] where we used to use the dequeued burst time.

I used a LinkedQueue here, but that does not matter. Any queue implementation would work.

When we stated the problem, we listed some edge cases. Let’s check the solution against them.

• If burstTimes is empty, the queue starts empty, the loop never runs, and we return an empty array.
• If every burst time is at most quantum, then Math.min(quantum, remaining[taskIndex]) runs each task to completion on its first turn, and no task is ever re-enqueued: the tasks run one after another, in input order.
• A task that finishes exactly at the end of its slice has remaining[taskIndex] == 0, so it is recorded as done instead of being re-enqueued with no work left. The Math.min line covers both “each task gets at most quantum units” and this boundary case.

You can also check the method against our running example: with burstTimes = [9, 2, 7] and quantum = 4, it returns [18, 6, 17].

The pattern here is using a queue to simulate a waiting line.