I'd like to find an algorithm that can solve the following problem:
Consider 4 groups of numbers:
- Group 1: [10, 100, 1000],
- Group 2: [101, 15, 2000],
- Group 3: [20, 1500, 100],
- Group 4: [150, 3000, 13].
I need to select one number from each group so that the difference between the maximum and minimum of the four selected numbers would be the smallest among all possible combinations.
In this example, the numbers 10, 15, 20, 13 give the difference 10 and it is the smallest. The answer for the problem above is 10, 15, 20, 13.
I wonder if there is an algorithm that can solve this problem and also scales relatively well for a large number of groups and the number of entries in each group.
EDIT: @aurelian-tutuianu proposed an algorithm of complexity $O(nk\log k)$ that involves sorting each group. I wonder what would be the best algorithm if it's impossible to sort those groups. For instance, for groups
- Group 1: [a1, a2, a3],
- Group 2: [b1, b2, b3],
- Group 3: [c1, c2, c3],
- Group 4: [d1, d2, d3],
where I can find a pairwise similarity between all elements but cannot sort them.