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. 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 2 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 this.

Is this the best way to approach this problem, or are there better data structures that I can use ?