[Algorithm]

Suppose a factory works round the clock and there is a need to optimise the performance of an important processing machine. There are n jobs to be processed. They are not available simultaneously, but their release times and processing times are known in advance. The jobs are numbered in accordance with their release times: job 1 becomes available at time r, and it has processing time p; job 2 becomes available at time r2, r2 r1, and it has processing time P2; jobj becomes available at time rj, r; > rj-1, and it has processing time pj; - job n becomes available at time in, in 2 rn-1, and it has processing time Pn. Due to the technological restrictions, it is required that the machine can process one job at a time, any job can be started at its release time or at any time later on; any job j can be pre-empted multiple times; if this happens the job should be resumed later and the total duration of all parts of that jobs should be equal to the job processing time pj. Additionally, in order to increase the throughput, the following scheduling policy is adopted: at each decision point, which corresponds to the release time or completion time of some job, the job to be processed next should have the smallest remaining processing time. To illustrate the described policy, consider the following instance with n = 8 jobs: Job j Pi ri 0 1 2 13 6 3 3 4 5 6 14 18 22 25 8 3 5 3 4 1 7 8 30 34 The Gantt chart of a schedule is presented below. Notice that job 1 is pre-empted at time r2 = 3 since remaining processing time of job 1 is larger than P2 = 6. The second part of job 1 is not pre-empted at time r3 = 14 since remaining processing time of job 1 is less than 23 = 8. The validity of the remaining part of the schedule can be checked similarly. 1 2 4 5 6 7 8 3 time 0 3 9 14 25 27 30 13 17 18 19 22 34 35 43 r1 12 14 r's 16 18 As all information about arriving jobs is available in advance, the factory wants to pre- calculate the starting times of the jobs and their parts according to the described policy. A straightforward algorithm can perform these calculations in O(n) time. There exists a faster, O(n log n)-time algorithm. It is not based on divide-and-conquer. Explain in a few sentences (say, 2-3 sentences) the underlying idea of the O(n log n)-time algorithm