Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Suppose we had 2 arrays of the same size with positive numbers and we wanted to pair up the elements of each array such that the total difference between the pairs is minimized.
The first thought would be to choose pairs with the minimum difference and so on. But it turns out the correct algorithm is to sort them and them pair accordingly.
Any ideas on how to prove that the latter algorithm correctly minimizes the sum of differences?
Let's follow Karolis's suggestion. Consider any solution with pairs $(a,b)$ and $(A,B)$ with $a \leq A$ and $B \leq b$, and write $A = a + \delta$, $B = b - \epsilon$. If we instead pair them $(a,B),(A,b)$, then instead of $|a-b|+|A-B|$ we get $|a-B|+|A-b|$. So we want to show $$ |a-b|+|A-B| \geq |a-B|+|A-b|. $$ Substitute the expressions for $A,B$: $$ |a-b| + |a-b+\delta+\epsilon| \geq |a-b+\epsilon| + |a-b+\delta|. $$ In terms of $C = a-b$, this is $$ |C| + |C+\delta+\epsilon| \geq |C+\epsilon| + |C+\delta|. $$ Rearranging, this is the same as $$ |(C+\delta)+\epsilon| - |C+\delta| \geq |C+\epsilon| - |C|. $$ So we need to look at the function $D \mapsto |D+\epsilon| - |D|$, whose values are $$ |D+\epsilon| - |D| = \begin{cases} \epsilon & D \geq 0, \\ 2D+\epsilon & -\epsilon \leq D \leq 0, \\ -\epsilon & D \leq -\epsilon \end{cases} $$ We see that this is an increasing function of $D$, and so $C+\delta \geq C$ implies the inequality we want, $$ |(C+\delta)+\epsilon| - |C+\delta| \geq |C+\epsilon| - |C|. $$
