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.
Time Complexity of a selection problem
complexity theory;time complexity;set cover
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.