So say I have n numbers, where n is even. I want to pair the numbers such that the maximum sum of the pairs is minimized. For example -2, 3, 4, 5. The ideal pairing is (-2, 5), (3, 4), since its maximum sum is 7, and that is the minimal sum possible for a max sum in any pairing. The key to the algorithm is to sort the values from least to greatest. Then pair the least with the greatest, and so on, until you reach the center of the ordering.
Example: 3, -2, 4, 5
Algorithm sorts the values: -2 , 3, 4, 5
Then pairs first with last: (-2, 5)
Then pairs the next available first and last: (3, 4)
Terminates since no pairs left.
This is a greedy algorithm and I am trying to prove that it is always correct using a “greedy stays ahead” approach. My issue is that I am struggling to show that the algorithm’s maximum sum is always $ \leq$ optimal maximum sum. My intention was to suppose for contradiction that the optimal maximum sum is $ <$ the algorithm’s maximum sum. But I’m not sure how to find a contradiction. How would this proof go?