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 Atj .
For example, let n and S1 1,2 ,S2 machine 1, and J
3,m 3, J 1,2,3 , t1 1,t2 3,t3 5, 2,3 ,S3 1,2 , then assigning A 1,2 to
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 thejobsintoAandJ Ainsuchawaythatoneachdayi,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 105,1 m 2 106.
In each of the next m 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:
44 12 23 14 34
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
33 12 23 13
there is no perfect split, so your code should just output a 0 in the first line (and nothing else).