educative.io

Educative

Why `k+1` tasks in this solution?

In the solution for Scheduling Tasks (hard) , they have a sentence which states that

In each iteration, we will try to execute as many as k+1 tasks. 

Now how the heck did these guys arrive at k + 1 tasks? Why not k, why not k - 1? whats up with this magic number?

We need to make sure that the same tasks are k distance apart. For example:
[a, b, a], k=3

When we execute task “ a ” we can run k=3 more tasks before running “ a ” again. Hence, we can execute as many as k+1=4 tasks in one iteration. (the first task + 3 more tasks)

If for any iteration, we are not able to execute k+1 tasks, the CPU has to remain idle for the remaining time in the next iteration.

1 Like