# Time Complexity of a selection problem

I wonder what's the time complexity of the following selection problem I found while thinking of a string-matching problem.

[Assuming operations on integers take $O(1)$ time]

We are Given $m$ sets, with $n$ integer numbers each. We want to select exactly one integer from each set, to make a set S, such that $~ l = \max(S) - \min(S)~$ is minimized.

For example, n = 4, m = 3:

$S_1 = \{1, 43, 71, 101\}$

$S_2 = \{18, 53, 80, 107\}$

$S_3 = \{3, 16, 51, 208\}$

Now

$~S = \{43, 53, 51\}$

has one number from each set and

$~l = \max(S) - \min(S) = 53 - 43 = 10 ~$

wich is the minimum possible value of $l$ (I think).

First thing I tried was a reduction to the set cover problem, but I wasn't able to find one.

If you are trying to prove $NP$-Hardness of that problem, you need a reduction from (not to).

Anyway, I don't think this is $NP$-hard (unless $P = NP$, of course)

Suppose the $S_i$ are sorted.

Suppose you decide that element $x \in S_j$ will be minimum. Now in each other set, you can find the smallest element greater (or equal to) $x$ using binary search, and take the maximum among those.

Do this for each of the $mn$ numbers, assuming it is the minimum. Pick the best set you get. This gives you a polynomial time algorithm: $m \log n$ time for each of the $mn$ elements, giving an $O(m^2n \log n)$ time algorithm.

• @Haile: No questions? If you think this does not answer your question, can you clarify what exactly is your question? – Aryabhata Apr 21 '13 at 2:28
• Yes, the reduction was from, it was a language mistake. Yep, your answer is clear. Thank you! – Haile Apr 21 '13 at 13:02
• Nice solution. But your answer still doesn't resolve the complexity of this problem. We just know that its in P now. – rizwanhudda Apr 23 '13 at 20:39
• @rizwanhudda: Yes, I never claimed optimality of the solution. – Aryabhata Apr 23 '13 at 20:47