I have a list of integer pairs. The value of this list is the sum of the maximum values of each pair.
For
(0, 5) (20, 5) (6, 8)
the value would be
5 + 20 + 8 = 33
Given a list like this, I need to maximize its value. The only operation I can do is swap an element of a pair with another element of a different pair.
Edit: Just to clarify, I need to do this operation as many times as needed to obtain the maximum value, not just once.
For the example above I can do this
(6, 8) <> (0, 5)
The list would become
(0, 6) (20, 5) (5, 8) => value = 6 + 20 + 8 = 34
So in order to increase the value I'd need to find 2 pairs (a,b) (c,d) with min(a,b) > max(c,d) and then swap min(a,b) with max(c,d), right ? If no such pairs exist then the we cannot increase the value of the list.
Solution:
I need to keep the pairs sorted in descending order by the minimum value and in ascending order by the maximum value because I need to compare the pair with the greatest minimum to the one with smallest maximum.
I thought about using two heaps for this, a minheap which orders by maximums and a maxheap which orders by minimums. This way, each time I need to compare I can just compare the roots of the two heaps.
The problem is that I also need to update these values, by exchanging the minimum value of 1 pair with the maximum value of another pair and then reorder the heaps so I would need to also keep additional information for each heap node for the position in the other heap. Something like Dual heap in Double-ended priority queue.
Is this the best way to approach this problem, or are there better data structures that I can use?
