Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
What exactly happens when two workers finish at the same time? Do they choose jobs in numerical order again? I'm pretty sure you can do better by renumbering the tasks so that the fastest worker works on the first one, the second fastest on the second one and so on, then you can calculate when the next worker will be finished efficiently. –  chthonicdaemon May 25 '13 at 12:20
    
Always when two workers finish at the same time they choose jobs in numerical order: the one with lower identifier choosing the lowest numbered job that no one started doing and the other the second lowest numbered job. However I don't see how renumbering the workers may help. –  Stefan Czarnecki May 25 '13 at 13:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.