Min-max the component-wise sum of two sets
Let $f$ be an optimal solution in which $f(a_1) &lt; f(a_2)$ for some $a_1 &lt; a_2$. Let $g$ be obtained from $f$ by switching the values at $a_1$ and $a_2$:
$$
g(a) = \begin{cases} f(a_2) &amp; a = a_1, \\ f(a_1) &amp; a = a_2, \\ f(a) &amp; \text{otherwise}. \end{cases}
$$
Then
$$
\begin{align*}
a_1 + g(a_1) &amp;= a_1 + f(a_2) &lt; a_2 + f(a_2), \\
a_2 + g(a_2) &amp;= a_2 + f(a_1) &lt; a_2 + f(a_2), \\
a + g(a) &amp;= a + f(a) &amp; \text{otherwise}.
\end{align*}
$$
It follows that $\max g \leq \max f$.

Consider now $f$ as a permutation on $\{1,\ldots,n\}$: the first element is the index of $f(a_n)$, the second element is the index of $f(a_{n-1})$, and so on. It is a classical result that $f$ can be sorted by transposing pairs of numbers in the wrong order, an operation which corresponds to the transformation above (one way is to put $n,n-1,\ldots,2$ in their right place, if needed, in this order). The correctness of your algorithm immediately follows.

Comment: This sort of analysis is very reminiscent of the analysis of greedy algorithms.