1
$\begingroup$

Lets say I have four group

A [ 0, 4, 9] B [ 2, 6, 11] C [ 3, 8, 13] D [ 7, 12 ]

Now I need a number from each group(i.e a new group) E [num in A,num in B, num in C, num in D], such that the difference between the maximum num in E and minimum num in E should be possible lowest.What type of problem is this ? which graph algorithm will be better to solve this kind of problem ? Thanks in advance.

  • 0
    @Joe - from what I understand you have to find an option to get the minimum, not **all** options2012-08-25

1 Answers 1

2

I can't think of any reasonable way to represent this problem using graphs.

I suggest the following to deal with your problem:

1) keep the elements of each groups sorted .

denote $n$ as the total number of elements ($n=|A|+...+|D|)$, for each $M\in\{A,B,C,D\}$ denote$U_{M}$ as the union of the other groups with higher alphabetical order (for example $U_{B}=C\cup D)$.

2) since we have to choose one element from each group we have to choose one from $M$, for every element in $M$ find an element in$U_{M}$ s.t the difference is minimal (since the elements are sorted you can do this in $log(|U|)$ using binary search).

save this minimum in a variable and update it when you find a new minimum (also save the elements that gave you the minimum and the groups they came from so you can know what elements in what groups give this minimum)

At the end of this procedure you will know what two elements in which groups give you your minimum, of course you can take the other two elements for $E$ in an arbitrary way without it affecting the minimum.

The time complexity is $O(nlog(n))$ since for every $M$ it holds that $|M|\leq n$ and$|U_{M}|\leq n$.