1

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?

  • Is each pair unique? – Mike Nakis Dec 8 '15 at 11:44
  • @Mike Nakis no. There can be multiple pairs with the same values. – Adrian Dec 8 '15 at 11:46
1

I think you may be thinking about it too hard, or trying to complicate it more than necessary.

When a pair is to be modified, remove it from both heaps, modify it, then add it to both heaps.

One little issue you might encounter is that once you have found in one heap a pair that you want to alter, how to locate that pair in the other heap. If pairs are unique, this is not an issue. If pairs are not unique, then you may need to add a field to uniquely identify them. Unless the language you are using already provides some kind of identity. (For example, in Java, you could compare by reference.)

  • That is basically what I had in mind. I need to somehow store information about locating a pair on the other heap so I can make changes to it. It just seems a little inefficient to basically do two heap removals and two heap insertions, each of them O(logn), for each item. – Adrian Dec 8 '15 at 11:57
  • Considering the nature of the problem, I think O(2 log n) is about the best you could hope for. And it is not really inefficient. You are still sub-O(n). You should not be complaining! – Mike Nakis Dec 8 '15 at 12:01
0

Your problem can be broken down into two parts:

  • a sorting algorithm that takes a value from a given element
  • a method to choose which value to extract, given a feature name

So something like (python-like pseudocode):

data = new MyDataStructure()
#Insert some values into it..
#...

def extract_feature(myObject, feature_name):
   return myObject.getFeature(feature_name)


print sorted(data, (key=lambda x: extract_feature(x))

Re: your comment You are talking about datastructures, but what you are really after..is a sorting algorithm that can take an object type and change the a.compareTo(b) call on the fly. In other words, any datastructure will do. Your sorting algorithm just needs to know how to compute the key with which the sorting will be done.

Example: https://wiki.python.org/moin/HowTo/Sorting#Key_Functions

  • I do not see how this is relevant. – Adrian Dec 8 '15 at 10:41
  • The problem is not sorting the data one way or another. It's a question about whether the idea of the algorithm is correct and whether the double-ended priority queue is the best data structure to use. – Adrian Dec 8 '15 at 11:35
0

What you are really looking for is the sum of the highest 50% of the elements.

Given a set of n pairs, there are 2n elements. Let us split these elements into two sequences (not sets, elements can occur multiple times), s and t each containing n elements. We swap elements until it is true that for every element e in s and f in t, that e <= f.

Now you simply sum up the elements in t, giving us the result. This is very similar to sorting the elements in each pair, discarding the half of the elements that are smallest, and summing the rest.

The easy way to achieve these results is with the following algorithm:

  1. Split each pair in n into two numbers and insert them into list t.
  2. Sort the list t in descending order.
  3. Sum up the first c/2 elements where c is the count of elements in the list (guaranteed to be even).
  • I think you're right. I was overthinking it. What about the case where I can only do a maximum of K swaps ? This would not work anymore, and I'd have to do it my way right ? – Adrian Dec 9 '15 at 9:02
  • @Adrian correct, with a limited number of swaps this approach would not work. You could do some calculations ahead of time to determine the minimum number of swaps necessary to achieve the maximum result, or to determine a strategy to maximize the result if the actual maximum is not possible. – user22815 Dec 9 '15 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.