What type of algorithm should I use?

Question

Let's say I have four groups

A [0, 4, 9]

B [2, 6, 11]

C [3, 8, 13]

D [7, 12]

Now I need one number from each group (i.e. a new group) E [number A, number B, number C, number D], so the difference between the maximum number in E and the minimum number in E should be minimal. What type of problem? which graph algorithm would better solve this problem? Thanks in advance.

PS: I'm trying to solve this in java and sorry for the unspecified header.

Edit: Finally, I found what I'm really looking for http://rcrezende.blogspot.in/2010/08/smallest-relevant-text-snippet-for.html

Answer 1

• Combine the contents of each group into one array. Each element of the array must be a pair (number, group name).
• Sort this array by numbers.
• Push two iterators one by one. Move the first iterator when the elements of not every group are between these iterators. Move the second iterator when there is an element of each group between these iterators. See this question for more details.
• The minimum distance between iterators determines the optimal resulting group (you only need to discard unnecessary elements if there are several representatives of the same group).

---

Another algorithm:

• Sort the elements of each group (if they are not already sorted).
• Put a pair (number, group name) for the smallest elements of each group in the priority queue (min-heap, priority = number).
• Remove the smallest item from the queue and replace it with the next item from the same group.
• Repeat step 3 until there are no more elements in any group. Calculate max (queue) - min (queue) for each iteration, and if it is less than any previous value, update the result group with the best date.

Answer 2

I think you can do an exhaustive search, with quick completion, this is not as bad as it seems.

For example, if you select a number from A and B, you can select two numbers from C that are closest to these two numbers, using any other number may not give better results.

• For each element A: name it a , you are looking for numbers close to the interval (a, a)
• Now, for each group, select the closest numbers (you can do this with binary search). Now you have a new search interval, either (a, b1) or (b2, a)

Example:

• Choose 4 from A, going close to (4.4)
• A) Choose 2 from B, going close to (2,4)
• .... Select 3 from C, this is in the interval. search near (2.4)
• .... Choose 7 from D, interval (2.7), distance 5.
• B) Choose 6 from B, look close to (4.6)
• ....