# Choosing one number from each set so that the difference between maximum and minimum is minimized

Suppose I have four sets A={0, 4, 9}, B={2, 6, 11}, C={3, 8, 13}, and D={7, 12}.

I need to choose exactly one number from each of these sets, so that the difference between the largest and smallest chosen numbers is as small as possible.

What type of problem is this? Is there a graph algorithm that could be used to solve this problem?

• Is this question really about groups or is it actually about sets? Aug 25, 2012 at 20:29
• Edited for clarity Aug 26, 2012 at 1:38
• the tags seem random Aug 26, 2012 at 16:11
• I hope you enjoyed seeing people do duplicate work, but that is against some vague ethics. Please refrain from it in the future. Aug 27, 2012 at 15:06

In general minimum range matroid basis problems can be solved in $O(n\log n)$ time, plus $O(n)$ steps of a subroutine that finds a basis of a set with corank one: sort the elements from smallest to largest and then process the elements one by one. While you process the elements maintain an independent set $I$; when you process an element $e$, add $e$ to $I$ and, if that addition causes $I$ to become dependent, kick out the minimum weight element in the unique circuit of $I$. The minimum range basis is one of the sets $I$ that you found in this process: the one that has full rank and has as small a range between min and max as possible.
For your partition matroid special case it's easy to find the circuit in $I$ when it becomes dependent: a circuit happens when $e$ belongs to the same group as an element $f$ that you previously added, and $f$ is the element you should kick out of $I$. So the whole algorithm takes $O(n\log n)$ time, or possibly faster depending on how much time it takes to do the sorting step.