PROBLEM LINK
Author: Sergey Nagin
Tester: Sergey Kulik
Editorialist: Florin Chirica
DIFFICULTY
Hard
PREREQUISITES
sorting, logical analysis
PROBLEM
You are 2 computers and n jobs to run on them. Each process should run on both the computers. For each job, you are given
time for execution on the both the machines by A and B array respectively. Also parallel execution of
a job on both computers is not allowed. You have to give a order of running jobs on the computers which takes least total time.
EXPLANATION
Find lower bound on total time required
Let’s denote by A[i] the time needed for job i to be processed on first computer. Similarly define B[i] the time for job i to be
processed on the second computer. Also, let t be the minimal time all jobs are performed. Let’s find a lower bound for the t.
-
A job i can’t be processed on both computers simultaneously, so the minimal time for a job to be processed is A[i] + B[i]
(we process it on first computer, then do it immediately on the second one). We get that t >= A[i] + B[i]. -
Also, a computer can’t process two jobs simultaneously. Computer 1 needs to finish all its jobs and the minimal time to do it
is A[1] + A[2] + … + A[n]. So we get that t >= A[1] + A[2] + … + A[n]. -
Similarly for the second computer, t >= B[1] + B[2] + … + B[n].
So overall t >= max(A[i] + B[i], A[1] + A[2] + … + A[n], B[1] + B[2] + … + B[n]).
Lower bound is indeed achievable
Now we will consider several possible cases and show how lower bound is achievable in those cases.
Case 1: max(A[i] + B[i]) >= max(A[1] + A[2] + … + A[n], B[1] + B[2] + … + B[n])
In this case, we need to prove that we can finish all jobs in max(A[i] + B[i]) time. In this case, the strategy would be to run
the job with maximum A[i] + B[i] on first computer, then during that time run the all other jobs in second computer. Then similarly run
it on second computer. More formal arguments follow.
Let j be a process such that A[j] + B[j] = max(A[i] + B[i]). At time 0, we can start processing task j on the first computer and at time A[j]
task j on the second computer. So far, time needed is A[j] + B[j]. As we have A[1] + A[2] + … + A[n] <= A[j] + B[j].
We get that A[1] + A[2] + … + A[j - 1] + A[j + 1] + … + A[n] <= B[j]. This means, while the job j is running on computer 2,
all other jobs can be done on first computer. Similarly, all jobs on the second computer except j can be done before job A[j]
is finished on the first computer. This means, at moment A[j], all other jobs except B[j] will have been done on second computer.
Case 2: max(A[1] + A[2] + … + A[n], B[1] + B[2] + … + B[n]) > max(A[i] + B[i])
Here, t = max(A[1] + A[2] + … + A[n], B[1] + B[2] + … + B[n]).
Try the most intuitive ordering
Most basic idea would be to run the jobs one by one in the given order on first computer. Also intuitively for avoiding parallel processing
of jobs, you would try to process the first job as late as possible on the second computer. So your order of processing the jobs
will be completely reverse for both the computers.
Formally, for computer 1, let’s run job 1 from {0, A[1]}, job 2 from {A[1], A[1] + A[2]},
job 3 from {A[1] + A[2], A[1] + A[2] + A[3]} and so on. For computer 2, let’s run job 1 from {t - B[1], t}, job 2 from
{t - B[1] - B[2], t - B[1]}, job 3 from {t - B[1] - B[2] - B[3], t - B[1] - B[2]} and so on.
Jobs are getting intersected in this ordering
Though the schedule produces the wanted time t, however it might have a problem: for a job i, intervals from first computer and
from second computer of it might intersect. This is not allowed, since a job can be processed at most at one computer at a time.
Lets fix this problem by shuffling the ordering
Luckily, there is at most one job i, for which the ranges can intersect. Let’s try to fix this. Again most intuitive idea is to
try doing this job as early only first computer and as late on second computer.
Formally, Suppose the job for which the ranges intersect is i. Ranges are {t - B[1] - B[2] - … - B[i], t - B[1] - B[2] - … - B[i - 1]}
(for job i), {t - B[1] - B[2] - … - B[i - 1], t - B[1] - B[2] - … - B[i - 2]} (for job i - 1) … {t - B[1], t} for job 1.
The trick is to change the order of jobs:
job i to be processed between {t - B[i], t}.
job 1 to be processed between {t - B[i] - B[1], t - B[i]}
job 2 to be processed between {t - B[i] - B[1] - B[2], t - B[i] - B[1]}
and so on.
Proof that this change of order will work
Indeed, let’s add jobs to first and second computer as described.
When adding a job in first computer, its index will be > i. But on B there will be indexes <= i. Similarly, when adding a
job with index > i on B, on A all indexes will be <= i.
Hence, the only step left is to ensure that after we do the swap, no two intervals will intersect. This is equivalent to saying that
intervals of i won’t intersect (since all other intervals have no chance to intersect).
Interval of i from computer 1 is {A[1] + A[2] + … + A[i - 1], A[1] + A[2] + … + A[i]}. Interval of i from the second computer
is {t - B[i], t}.
We need to make sure that A[1] + A[2] + … + A[i] < t - B[i].
We leave as an exercise for the reader to show that sorting increasing by A[i] - B[i] indeed guarantees this.