Select pairs of numbers with the minimum overall difference

Question

Given n pairs of numbers, select k pairs so that the difference between the minimum value and the maximum value is minimal. Note that 2 numbers in 1 pair cannot be separated. Example (n=5, k=3):

INPUT        OUTPUT (return the index of the pairs)
5 4          1 2 4
1 5
9 8
1 0
2 7

In this case, choosing (5,4) (1,5) (1,0) will give a difference of 5 (max is 5, min is 0). I'm looking for an efficient way (n log n) of doing this since the input will be pretty large and I don't want to go through every possible case.

Thank you.

NOTE: No code is needed. An explanation of the solution is enough.

Answer 1

Here's a method with O(n log n) time complexity:

First sort the array according to the smaller number in the pair. Now iterate back from the last element in the sorted array (the pair with the highest minimum).

As we go backwards, the elements already visited will necessarily have an equal or higher minimum than the current element. Store the visited pairs in a max heap according to the maximal number in the visited pair. If the heap size is smaller than k-1, keep adding to the heap.

Once the heap size equals k-1, begin recording and comparing the best interval so far. If the heap size exceeds k-1, pop the maximal element off. The heap is guaranteed to contain the first k-1 pairs where the minimal number is greater than or equal to the current minimal number and the maximal is smallest (since we keep popping off the maximal element when the heap size exceeds k-1).

Total time O(n log n) for sorting + O(n log n) to iterate and maintain the heap = O(n log n) in total.

Example:

5 4
1 5
9 8
1 0
2 7

k = 3

Sort pairs by the smaller number in each pair:
[(1,0),(1,5),(2,7),(5,4),(9,8)]

Iterate from end to start:
i = 4; Insert (9,8) into heap
i = 3; Insert (5,4) into heap
i = 2; Range = 2-9
i = 1; Pop (9,8) from heap; Range = 1-7
i = 0; Pop (2,7) from heap; Range = 0-5

Minimal interval [0,5] (find k matching indices in O(n) time)