Let $x_{1}<x_{2}<\ldots <x_{k}$ be all the elements of $\cup^{n}_{i=1} A_{i}\cup B_{i}$. Also let $d$ be the largest difference between consecutive elements of a set when we arrange them in descending order. If $\exists i$ such that $x_{i}$ is an element of exactly one of the sets, say $A_{j}$, then since $x_{i}\not\in B_{r}$ $\forall 1\leq r\leq n$ we can select an element $x_{a}\in A_{j}\cap B_{1}$ and add $x_{i}$ to $B_{1}$. Notice that since $x_{i},x_{a}\in A_{j}$ this implies that by adding $x_{i}$ to $B_{1}$ we won't increase $d$ since $x_{a}\in B_{1}$ as well. This implies that we can assume that $\forall i$, $x_{i}\in A_{i_{1}}\cap B_{i_{2}}$ for some $1\leq i_{1},i_{2}\leq n$. Now notice that we can simplify the problem condition using the following algorithm (inspired by an idea from IMO 2021 P2): $\textbf{1)}$ If there exists some $z\in \mathbb{Z}_{>0}$ such that $z\in \cup^{n}_{i=1} A_{i}\cup B_{i}$, $z+1\not\in \cup^{n}_{i=1} A_{i}\cup B_{i}$ and $\exists c>1$ such that $z+c\in \cup^{n}_{i=1} A_{i}\cup B_{i}$, then we can strictly decrease $S=\sum\limits_{1\leq i,j\leq n} |x_{i}-x_{j}|$ without increasing $d$. $\textbf{2)}$ If $|A_{i}\cap B_{j}|>1$ for some $1\leq i,j\leq n$, then we can decrease $k$ without increasing $d$. $\textbf{Proof that the algorithm can be performed:}$ For $\textbf{1)}$ we can notice that if we replace all $x_{i}>z$ by $x_{i}-c+1$ we'll still have $A_{i}\cap A_{j}= \emptyset$ and $B_{i}\cap B_{j}= \emptyset$. Also we aren't deleting any elements, so the condition $A_{i}\cap B_{j}\neq \emptyset$ will be satisfied. With this operation we either don't change $|x_{i}-x_{j}|$ or decrease it, so $d$ isn't increased and $S$ is strictly decreased. For $\textbf{2)}$ we can notice that if WLOG $y>z$ and $y,z\in A_{i}\cap B_{j}$ then we can delete $y$ from all sets it's in and perform $\textbf{1)}$ since now $y\not\in\cup^{n}_{i=1} A_{i}\cup B_{i}$ (or if $y$ had been the maximal element in the union of all sets, i.e. when we can't perform $\textbf{1)}$, then simply note that $S$ strictly decreases). Because $A_{i}\cap A_{j}= \emptyset$ and $B_{i}\cap B_{j}= \emptyset$ before we delete $y$, this means that $y$ is an element only of $A_{i}$ and $B_{j}$ for fixed indeces $i$ and $j$. Thus by deleting $y$ we only have to worry about whether $A_{i}\cap B_{j}$ is an empty set, but we assumed that there exists $z\in A_{i}\cap B_{j}$, so all intersection of sets requirements are met. $\textbf{Proof that the algorithm is finite:}$ Notice that when performing $\textbf{1)}$ or $\textbf{2)}$ we strictly decrease $S$ which is a non-negative integer, thus the algorithm is finite. Let's consider what has happened to the sets when the algorithm finishes. We aren't able to perform $1)$, so $x_{i+1}-x_{i}=1$ $\forall i$. Also, we can't perform $2)$, so $|A_{i}\cap B_{j}|=1$ $\forall 1\leq i,j\leq n$. Above we also mentioned that we can assume that every element of the union of all sets is an element of one $A$ set and one $B$ set. Combining these three results we conclude that $|A_{i}|=|B_{i}|=n$ $\forall 1\leq i\leq n$ and that the elements of the sets are $n^2$ consecutive integers (WLOG let them be $1,2, \ldots ,n^2$ because otherwise we ca shift all of them by a constant and nothing will change). \[ \begin{tabular}{ |c|c|c|c|c| } \hline ~ & $B_{1}$ & $B_{2}$ & $B_{3}$ & $B_{4}$\\ \hline $A_{1}$ & $\textcolor{red}{1}$ & $\boxed{\textcolor{red}{2}}$ & $\boxed{\textcolor{red}{6}}$ & $\textcolor{green}{11}$ \\ \hline $A_{2}$ & $\textcolor{red}{3}$ & $\textcolor{green}{8}$ & $\textcolor{red}{5}$ & $\boxed{\textcolor{red}{7}}$ \\ \hline $A_{3}$ & $\boxed{\textcolor{red}{4}}$ & $13$ & $\textcolor{green}{9}$ & $16$\\ \hline $A_{4}$ & $\textcolor{green}{15}$ & $12$ & $10$ & $14$\\ \hline \end{tabular} \]\[\text{Here is an example for $n=4$:}\]Let $M_{t}$ be the set $\{1,2,\ldots ,t\}$ such that $t$ is the smallest positive integer such that $M_{t}$ either has elements in every $A_{i}$ or in every $B_{i}$ (put another way, if we consecutively colour the numbers $1,2, \ldots$ in red, when are we first going to get a red element in every row or every column). WLOG let there be a red number in every column. This implies that every column has at least one number outside of $M_{t}$. Consider the following sets: let $T$ be the set of the biggest element of $B_{i}\cap M_{t}$ for all $i$ and $L$ be the set of the smallest element of $B_{i}\setminus (B_{i}\cap M_{t})$ (such a number always exists as we pointed out above that every column has an element outside $M_{t}$ otherwise there would have been a previous point in time when $M_{t}$ had an element in every row, contradiction with the minimality of $t$). In the grid, the set $T$ are the boxed numbers and the set $L$ are the green numbers. Notice that $\min\limits_{s\in T} s\leq k-(n-1)=k-n+1$ since $s\in T\subset M_{t}\Longrightarrow s\leq k$, but $T$ has $n$ elements, so the least number is at most $k-n+1$. However, if we consider the element of $L$ which is in the same column as $s$, we see that obviously, it isn't in $M_{k}$ by definition, so it's at least $k+1$, but also by definition this number is the smallest number in this column which is larger than $s$, thus we have a difference of at least $(k+1)-(k-n+1)=n$ (in the diagram we have $8-2=6>4$). It's easy that this minimal difference can be achieved, for example, consider: \[A_{i}=\{(i-1)n+x|1\leq x\leq n\}\text{ and } B_{i}=\{i+xn|0\leq x\leq n-1\}\]\[\begin{tabular}{ |c|c|c|c|c|c|c| } \hline ~ & $B_{1}$ & $B_{2}$ & $B_{3}$ & $ \ldots $ & $B_{n-1}$ & $B_{n}$ \\ \hline $A_{1}$ & $1$ & $2$ & $3$ & $\ldots$ & $n-1$ & $n$ \\ \hline $A_{2}$ & $n+1$ & $n+2$ & $n+3$ & $\ldots$ & $2n-1$ & $2n$ \\ \hline $A_{3}$ & $2n+1$ & $2n+2$ & $2n+3$ & $\ldots$ & $3n-1$ & $3n$ \\ \hline $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\ddots$ & $\vdots$ & $\vdots$\\ \hline $A_{n-1}$ & $n^2-2n+1$ & $n^2-2n+2$ & $n^2-2n+3$ & $\ldots$ & $n^2-n-1$ & $n^2-n$\\ \hline $A_{n}$ & $n^2-n+1$ & $n^2-n+2$ & $n^2-n+3$ & $\ldots$ & $n^2-1$ & $n^2$\\ \hline \end{tabular} \]Thus the answer to the problem is $n$.

Fixed @Below. Thanks to dgrozev for pointing out my flaw! The answer is $n$. Construction: $A_j=\{j, j+n, \cdots, j+(n-1)n\}, B_j=\{(j-1)n+1, \cdots, jn\}$ Proof of optimality: Consider a $n\times n$ grid. The square in the $i$th row and $j$th column of the grid is an element in $A_i\cap B_j$. Fill the numbers in the square in increasing order (since $A_i\cap A_j=B_i\cap B_j=\emptyset$ a number can be in at most one square). Consider the earliest moment when there is a square on every row or a square on every column. WLOG, there is a square on every row, and in the moment immediately before this, there is a row and a column with no filled squares. Therefore, there doesn't exist a full row, since my last move must fill a different row. Let $X$ be the number at this point. At this point, sort the rows in decreasing order of when the next number is filled. The first row $R$ (i.e. latest touched row after X) must have a number at least $n+X$ since each of the $n-1$ other rows must have a number (i.e. $1+X,\cdots,n+X-1$ must be filled in other rows already). At this point the max number in $R$ is at least $n+X$ At $X$, the max number in $R$ is at most $X$, and $1+X,\cdots,n+X-1$ are not in this row. Therefore, this row, which corresponds to $a_R$, has two adjacent elements (when sorted in increasing order) with difference at least $n$. Motivation: Think of $A_i\cap B_j$ as a grid. This is essentially a grid problem.

CANBANKAN wrote: ... WLOG one row is fully filled before one column is fully filled. Consider the moment when this happens, when $X$ is filled. This means in each column there is an unfilled square. Label them $s_1,\cdots,s_n$. If $s_n$ is filled last, it is at least $n+X$ so the answer is at least $n$. It may happen a column an a row are filled simultaneously. Say, when $X$ is filled, it completes the column and the row it belongs to. This is the right idea, but it should be fixed.

I commented on this problem on my blog.

When you delete y from Ai and Bj, the value of d might increase already? Marinchoo wrote:

Let $x_{1}<x_{2}<\ldots <x_{k}$ be all the elements of $\cup^{n}_{i=1} A_{i}\cup B_{i}$. Also let $d$ be the largest difference between consecutive elements of a set when we arrange them in descending order. If $\exists i$ such that $x_{i}$ is an element of exactly one of the sets, say $A_{j}$, then since $x_{i}\not\in B_{r}$ $\forall 1\leq r\leq n$ we can select an element $x_{a}\in A_{j}\cap B_{1}$ and add $x_{i}$ to $B_{1}$. Notice that since $x_{i},x_{a}\in A_{j}$ this implies that by adding $x_{i}$ to $B_{1}$ we won't increase $d$ since $x_{a}\in B_{1}$ as well. This implies that we can assume that $\forall i$, $x_{i}\in A_{i_{1}}\cap B_{i_{2}}$ for some $1\leq i_{1},i_{2}\leq n$. Now notice that we can simplify the problem condition using the following algorithm (inspired by an idea from IMO 2021 P2): $\textbf{1)}$ If there exists some $z\in \mathbb{Z}_{>0}$ such that $z\in \cup^{n}_{i=1} A_{i}\cup B_{i}$, $z+1\not\in \cup^{n}_{i=1} A_{i}\cup B_{i}$ and $\exists c>1$ such that $z+c\in \cup^{n}_{i=1} A_{i}\cup B_{i}$, then we can strictly decrease $S=\sum\limits_{1\leq i,j\leq n} |x_{i}-x_{j}|$ without increasing $d$. $\textbf{2)}$ If $|A_{i}\cap B_{j}|>1$ for some $1\leq i,j\leq n$, then we can decrease $k$ without increasing $d$. $\textbf{Proof that the algorithm can be performed:}$ For $\textbf{1)}$ we can notice that if we replace all $x_{i}>z$ by $x_{i}-c+1$ we'll still have $A_{i}\cap A_{j}= \emptyset$ and $B_{i}\cap B_{j}= \emptyset$. Also we aren't deleting any elements, so the condition $A_{i}\cap B_{j}\neq \emptyset$ will be satisfied. With this operation we either don't change $|x_{i}-x_{j}|$ or decrease it, so $d$ isn't increased and $S$ is strictly decreased. For $\textbf{2)}$ we can notice that if WLOG $y>z$ and $y,z\in A_{i}\cap B_{j}$ then we can delete $y$ from all sets it's in and perform $\textbf{1)}$ since now $y\not\in\cup^{n}_{i=1} A_{i}\cup B_{i}$ (or if $y$ had been the maximal element in the union of all sets, i.e. when we can't perform $\textbf{1)}$, then simply note that $S$ strictly decreases). Because $A_{i}\cap A_{j}= \emptyset$ and $B_{i}\cap B_{j}= \emptyset$ before we delete $y$, this means that $y$ is an element only of $A_{i}$ and $B_{j}$ for fixed indeces $i$ and $j$. Thus by deleting $y$ we only have to worry about whether $A_{i}\cap B_{j}$ is an empty set, but we assumed that there exists $z\in A_{i}\cap B_{j}$, so all intersection of sets requirements are met. $\textbf{Proof that the algorithm is finite:}$ Notice that when performing $\textbf{1)}$ or $\textbf{2)}$ we strictly decrease $S$ which is a non-negative integer, thus the algorithm is finite. Let's consider what has happened to the sets when the algorithm finishes. We aren't able to perform $1)$, so $x_{i+1}-x_{i}=1$ $\forall i$. Also, we can't perform $2)$, so $|A_{i}\cap B_{j}|=1$ $\forall 1\leq i,j\leq n$. Above we also mentioned that we can assume that every element of the union of all sets is an element of one $A$ set and one $B$ set. Combining these three results we conclude that $|A_{i}|=|B_{i}|=n$ $\forall 1\leq i\leq n$ and that the elements of the sets are $n^2$ consecutive integers (WLOG let them be $1,2, \ldots ,n^2$ because otherwise we ca shift all of them by a constant and nothing will change). \[ \begin{tabular}{ |c|c|c|c|c| } \hline ~ & $B_{1}$ & $B_{2}$ & $B_{3}$ & $B_{4}$\\ \hline $A_{1}$ & $\textcolor{red}{1}$ & $\boxed{\textcolor{red}{2}}$ & $\boxed{\textcolor{red}{6}}$ & $\textcolor{green}{11}$ \\ \hline $A_{2}$ & $\textcolor{red}{3}$ & $\textcolor{green}{8}$ & $\textcolor{red}{5}$ & $\boxed{\textcolor{red}{7}}$ \\ \hline $A_{3}$ & $\boxed{\textcolor{red}{4}}$ & $13$ & $\textcolor{green}{9}$ & $16$\\ \hline $A_{4}$ & $\textcolor{green}{15}$ & $12$ & $10$ & $14$\\ \hline \end{tabular} \]\[\text{Here is an example for $n=4$:}\]Let $M_{t}$ be the set $\{1,2,\ldots ,t\}$ such that $t$ is the smallest positive integer such that $M_{t}$ either has elements in every $A_{i}$ or in every $B_{i}$ (put another way, if we consecutively colour the numbers $1,2, \ldots$ in red, when are we first going to get a red element in every row or every column). WLOG let there be a red number in every column. This implies that every column has at least one number outside of $M_{t}$. Consider the following sets: let $T$ be the set of the biggest element of $B_{i}\cap M_{t}$ for all $i$ and $L$ be the set of the smallest element of $B_{i}\setminus (B_{i}\cap M_{t})$ (such a number always exists as we pointed out above that every column has an element outside $M_{t}$ otherwise there would have been a previous point in time when $M_{t}$ had an element in every row, contradiction with the minimality of $t$). In the grid, the set $T$ are the boxed numbers and the set $L$ are the green numbers. Notice that $\min\limits_{s\in T} s\leq k-(n-1)=k-n+1$ since $s\in T\subset M_{t}\Longrightarrow s\leq k$, but $T$ has $n$ elements, so the least number is at most $k-n+1$. However, if we consider the element of $L$ which is in the same column as $s$, we see that obviously, it isn't in $M_{k}$ by definition, so it's at least $k+1$, but also by definition this number is the smallest number in this column which is larger than $s$, thus we have a difference of at least $(k+1)-(k-n+1)=n$ (in the diagram we have $8-2=6>4$). It's easy that this minimal difference can be achieved, for example, consider: \[A_{i}=\{(i-1)n+x|1\leq x\leq n\}\text{ and } B_{i}=\{i+xn|0\leq x\leq n-1\}\]\[\begin{tabular}{ |c|c|c|c|c|c|c| } \hline ~ & $B_{1}$ & $B_{2}$ & $B_{3}$ & $ \ldots $ & $B_{n-1}$ & $B_{n}$ \\ \hline $A_{1}$ & $1$ & $2$ & $3$ & $\ldots$ & $n-1$ & $n$ \\ \hline $A_{2}$ & $n+1$ & $n+2$ & $n+3$ & $\ldots$ & $2n-1$ & $2n$ \\ \hline $A_{3}$ & $2n+1$ & $2n+2$ & $2n+3$ & $\ldots$ & $3n-1$ & $3n$ \\ \hline $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ & $\ddots$ & $\vdots$ & $\vdots$\\ \hline $A_{n-1}$ & $n^2-2n+1$ & $n^2-2n+2$ & $n^2-2n+3$ & $\ldots$ & $n^2-n-1$ & $n^2-n$\\ \hline $A_{n}$ & $n^2-n+1$ & $n^2-n+2$ & $n^2-n+3$ & $\ldots$ & $n^2-1$ & $n^2$\\ \hline \end{tabular} \]Thus the answer to the problem is $n$.

CANBANKAN's proof is exactly one of the proofs of IMO Shortlist 1988 P4. One just needs to pay attention to the details in order to extract two adjacent elements in a set when arranged in decreasing order.