Finding optimal price in a sale

Question

A furniture store is having a sale: purchase two items at the price of the more expensive one. John, having just moved to a new house, rushed into the store and chose $2k$ items of furniture, $f_1, f_2, \dots, f_{2k}$. The items are priced $p_1, p_2, \dots, p_{2k}$, respectively. Help John arrange the items in pairs so that the overall cost of the $2k$ items is minimal. Suggest an algorithm that runs in time $O(k\log k)$ and prove its correctness and running time.

Ok, so it sounds not too complicated: first, I will sort all the $2k$ items by their prices to array, and then each cell and his next are one couple. This takes time $O(k\log k)$.

How can I prove the correctness of what I suggest? I thought about assuming that there is a cheaper solution to get a contradiction but I dont know how to prove this.

Answer 1

Let's do the case $k = 2$. If the prices are $p_1 \geq p_2 \geq p_3 \geq p_4$ then there are three possible pairings $(p_1,p_2),(p_3,p_4);(p_1,p_3),(p_2,p_4);(p_1,p_4),(p_2,p_3)$ with cost $p_1+p_3;p_1+p_2;p_1+p_2$. So the first pairing is the best.

There are several ways to show that this pairing strategy is optimal in general. You might start by showing that given an arbitrary pairing in which $p_1$ is not matched with $p_2$, there is a way to modify it so that $p_1$ is matched with $p_2$, and the overall cost is lower. This leads to one proof.

Another idea is to show directly that the cost is always at least $p_1+p_3+\cdots$. For example, $p_1$ is always the largest in its pair, and $p_3$ is either the largest in its pair, or it is paired with $p_2>p_3$ or with $p_1>p_3$. You have to modify this argument so that you don't double count prices (for example, if $p_1$ is paired with $p_3$ and you follow the argument as stated, you will count $p_1$ twice).

There might be other ways to prove it, so if you have other ideas, by all means go ahead and try them out.