Time Complexity of a selection problem
-
16-10-2019 - |
Question
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.
Solution
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.