Let’s say we have n jobs numbered from 1 upto n and k workers numbered from 1 upto k.

All the jobs are equally difficult, but some workers are more efficient than others, so we are given the time it takes for each worker to perform his job. In fact no two workers are able to finish their jobs in the same time.

At first all the workers take care of the job numbered the same as them (first takes the first, second takes the second job etc.).

If someone finishes his job, he starts doing the job with the lowest number that no one has started doing. In case of a draw (two or more workers finish at the same time) the worker with lower identifier starts doing the lower numbered job, the other the higher numbered.

Workers work until all the jobs have been done.

For each worker, we would like to return the number of the last job he completed.

Example:
n = 10
k = 3
workers efficiency: 1->3, 2->5, 3->6

At first workers one, two, three start doing jobs: 1,2,3.
At time 3 one finishes his job and starts doing 4.
At time 5 two starts doing 5.
At time 6 both one and three finish their jobs – they start doing 6 and 7 respectively.
At time 9 one start doing 8.
At time 10 two start doing 9.
And finally at time 12 one start doing 10, the last job.
Therefore the answer is: 1->10, 2->9, 3->7.

It is easy to solve this problem by simulating this procedure maintaining a priority queue of workers. The running time of this algorithm would be O(nlogn).

I am wondering, how would one solve this problem faster, without simulating, for large values of n.