It's a nice problem My Solution : Let $max$ of $RHS$ is at $i=m$ let us call it $c$ (WLOG $a'_m\geq b'_m$) Consider the numbers '$b'_1,b'_2......b'_m,a'_m.....a'_n$ As there are $n + 1$ numbers altogether and only $n$ places in the initial sequence there must exist an index $j$ such that we have $a_j$ among $a'_m.....a'_n$ and $b_j$ among '$b'_1,b'_2......b'_m$ now , we have also $b_j\leq b'_m < a'_m\leq a_j$ Hence we have $|a_j-b_j\geq|a'_m-b'_m|$ so we are done.

Arrange the $a_{i}$ sequence to be increasing and align the $b_{i}$ sequence accordingly. Whenever $b_{i}>b_{j}$ we can alway replace between the two elements to obtain $max\{|a_{i}-b_{j}|,|a_{j}-b_{i}|\}\geq max\{|a_{i}-b_{i}|,|a_{j}-b_{j}|\}$. This way we can build a new sequence with decreasing maximal difference values until we reach the point when all the $b_{i}$ are increasing.