01204212/job queue

from 01204212

Job queue 1

You have n jobs to be executed in k servers, called server 0, server 1,..., and server k-1 (1 <= n <= 100,000; 1 <= k <= 100). These n jobs are job 0, job 1, job 2,..., job n-1. Each job i has to be processed by server s[i].

All jobs arrive to our system in order from job 0 to job n-1, and when it arrives it goes to the server that will process it. Each server processes jobs in the order that they arrive to the server. We assume that before the system starts processing any jobs, all jobs arrive at our system and are assigned to appropriate server queues.

The system works in synchronous rounds. Every server takes 1 unit of time to process any job. Although every server should finish working at the same time, we assume that server 0 finishes slightly faster server 1, server 1 finishes slightly faster than server 2, and so on. In this way we can distinguish the time that each job finished its processing. Finally, after each server finishes processing the current job, it takes next job in the queue to process for the next round.