This problem can be solved greedily. First remove all digits that are present in both arrays since they can be used as prefix of the number and we keep difference of high order digits as low as possible. Add them to the numbers from lower digits to higher digits in order to obtain smallest $n_1$ at the end. Observation: after this process is done all remaining digits in both arrays are different (but this is not very relevant).
Brute force the next digit of $n_1$, there are at most 9 possible digits that can be used for $n_1$. Fix a digit $d$ not used yet in the first array. Once $d$ is fixed as the next digit of $n_1$ use the largest digit lower than $d$ for $n_2$ (if no such digit exists continue with next digit for $n_1$).
After we have this prefix for $n_1$ and $n_2$ we already know that the inequality $n_1 > n_2$ holds, whatever order we use for following digits. In order to minimize $n_1 - n_2$ we should order remaining digits from first array in such a way that $n_1$ is minimized and order remaining digits from second array in such a way that $n_2$ is maximized. For the first case we should add remaining digits of $n_1$ in non-decreasing order, and for $n_2$ in non-increasing order.
Next is the pseudo-code for the explained algorithm. Notice that $n_1$ and $n_2$ are treated as string, not like numbers, so addition means concatenation. Also, instead of dealing with array of digits as input, convert them to array of frequency, $F_i(d)$ denotes how many times digit $d$ can be used for number $n_i$.
F1 = Frequency of each digit in first array.
F2 = Frequency of each digit in first array.
n1 = ""
n2 = ""
# Remove common digits in both arrays
for d in [0..9]:
while F1[d] > 0 and F2[d] > 0:
n1 += d, n2 += d
F1[d] -= 1, F2[d] -= 1
# Brute force next digit for number n1
for d1 in [1..9]:
# Ignore digit if it is not available
if F1[d1] == 0:
d2 = None
# Iterate backwards and find higher digit available for d2
for d2_it in [d1 - 1..0]:
if F2[d2_it] > 0:
d2 = d2_it
# If there is no available next digit for n2 continue
if d2 is None:
tmp_n1 = n1 + d1
tmp_n2 = n2 + d2
# Add next digits greedily
for d in [0..9]:
for i in [0..F1[d]):
tmp_n1 += d
for d in [9..0]:
for i in [0..F2[d]):
tmp_n2 += d
# Check difference of this pair
# and keep better pair accordingly to problem restrictions.
# This function will be called at most 9 times.
report tmp_n1, tmp_n2
report will be called 0 times in case there is no valid answer.