CODEWITHSUNDEEP
algorithm
user2637293
user2637293

Reputation: 351

How to prove a correctness of this following algorithm?

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 furnitures: f1, f2, ..., f2k−1, f2k. The items are priced p1, p2, ..., p2k−1, p2k, respectively. Help John arrange the furnitures in pairs so that the overall cost of the 2k items is minimal. Suggest an algorithm that runs in O(klogk), prove its correctness and running time.

Ok, so it sounds not to much complicated: first, i will sort all the 2k furnitures by their prices to array, and then each cell and his next are one couple.takes O(klogk).

How can i prove the correctness of what i suggest? i thought about assuming that there is more minimal solution and get a contradict but i dont know how to prove this. tnx a lot!

Upvotes: 1

Views: 92

Answers (1)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 71009

You want to buy all 2k pieces of furniture therefor each piece will be in exactly one pair. Now lets consider the pieces in decreasing order of their price. The most expensive piece will need to go in a pair and as it is most expensive, it will be more expensive than the other piece in the pair. Thus you can buy any piece of furniture for free with it. Let's assume that the best solution groups the most expensive piece with a piece of price X and let's further assume that this piece is not the second in terms of price(let's denote the second price piece S). Now S will be in a pair of its own and the price of this pair can not possibly be higher than the price of S. Now if we change the places of S and X the prices of all pairs but the ones where X used to be and the one where S used to be will remain the same. As S is now group with the most expensive element the price of this pair also stays the same. As for the pair where X now is - it can not possibly increase, because that would mean that X is more expensive than S, which is a contradiction.

Therefor the new solution also is optimal and as a consequence there always exists a solution where the most expensive element is grouped with the second to last. Now you can use induction to prove the correctness of your approach.

Upvotes: 2

Related Questions