1. (Job Assignment To Two Processors) Suppose we have two pro-
cessors and a set of jobs J 1, . . . , n , where job j has a processing
time tj 0. Over the next m n days, two jobs will be processed on
each day; we denote by Si the set of two jobs for day i; in other words,
Si 1, . . . , n , Si 2. A job will typically appear in multiple sets
1
Si. Given the sets S1, . . . , Sm and the processing times t1, . . . , tn, we
need to decide on which processor to run each job (and this processor
is then fixed for the entire set of m days); the goal is to do this in
such a way that the maximum work load (over the m days and two
processors) is minimized.
More precisely, a job assignment is a partition of the set of jobs into
A and J A, where jobs in A will be processed on processor 1, and
jobs in J A will be processed on processor 2. The objective of the
job assignment problem is to find A that minimizes the maximum
load over the m days and two processors, i.e., we want A to minimize
maxi 1,…,mmax j A Si tj , j Si A tj .
For example, let n 3,m 3, J 1, 2, 3 , t1 1, t2 3, t3 5,
and S1 1, 2 , S2 2, 3 , S3 1, 2 , then assigning A 1, 2 to
machine 1, and J A 3 to machine 2 gives the following loads:
day 1: 1+3=4 for machine 1, 0 for machine 2;
day 2: 3 for machine 1, 5 for machine 2;
day 3: 1+3=4 for machine 1, 0 for machine 2.
So the maximum load is 5.
We will say an input is perfectly splittable if it is possible to partition
the jobs into A and J A in such a way that on each day i, both
processors have only one job to process, i.e., A Si 1 and Si A
1. We call such a partition a perfect split.
The previous example is perfectly splittable, because we can take A
1, 3 , J A 2 . However, not every input is perfectly splittable; for
example, if we had an extra day S4 1, 3 in the previous example,
then the instance is not perfectly splittable.
If an instance has a perfect split, then this partition gives an optimal
solution to the job assignment problem (because the processing time
of the longest job is a lower bound on the maximum load of a solution,
and the maximum load of a perfect split (if it exists) meets this lower
bound so it must be optimal).
Implement an algorithm that determines in O m time whether an
instance is perfectly splittable. Hint: it will be useful to read sections
3.1-3.4.
Input / output formatting and requirements. Your algorithm
is to read data from stdin in the following format:
2
The first line has two integers, n and m (separated by a space).
All test cases will have 1 n 2 10
5
, 1 m 2 10
6
.
In each of the nextm lines, the i-th line contains 2 space separated
numbers representing the two jobs in Si (with each job being a
number in 1, . . . , n ).
(Note that we are not giving the processing times of the jobs, because
they are not relevant for your task this week; next week you will be
asked to solve (on paper; no coding) the problem of finding the optimal
solution also for instances that are not perfectly splittable, and there
your algorithm will need to use the jobs’ processing times.)
Your algorithm should output data to stdout in either 1 or n 1 lines:
The first line should be 1 if there exists a perfect split and 0 if
not;
If the first line is 0, you should not output anything else; if you
output 1 on the first line, the j 1 -th line should have the
number 1 or 2 depending on whether your solution assigns job j
to machine 1 or 2.
Example. When the input is:
4 4
1 2
2 3
1 4
3 4
there are 4 jobs, and 4 days, with S1 1, 2 , S2 2, 3 , S3
1, 4 , S4 3, 4 . There is a perfect split for this instance, by putting
jobs on one machine and the even numbered jobs on the other machine,
so your output could be:
1
1
2
1
2
If the input is:
3
3 3
1 2
2 3
1 3
there is no perfect split, so your code should just output a 0 in the
first line (and nothing else).
4