Maximum number of pairings of elements in a sequence

Question

I'm given n numbers a_1,a_2,...,a_n and they are given two me in and non-decreasing sequence, meaning a_1<=a_2<=...<=a_n in an array and I can pair two of them, say a_i and a_j if and only if 2a_i <= a_j. How many disjoint pairings can I maximally make?

I'm at a total loss here. I tried to do it greedily. Say I pair the largest one with the smallest one, erase them from sequence and proceed recursively. But that's wrong, because for 1,2,3,8 I would get one pair (1,8), but I can make two pairs (1,2) and (3,8). Based on that counterexample I tried to solve it differently. Say I pair a_i with the first number that I can. Then there's this counterexample 1,3,4,6. I would again get one pair (1,3), but in reality I can make two pairs (1,4) and (3,6).

Can anybody give me a hint about how to proceed?

I think that the following n-element table would be useful. For elements a_1,...,a_n tab[j] would denote the number of elements, for which 2a_i is smaller than a_j. This table can simply be computed in O(n) time. But I don't know how to use it correctly.

Answer 1

Observe that the best case is where you can split the array in the middle and match the first half with the second half, so the maximum possible answer is n / 2.

1 2 3 4 | 5 6 7 8

1 -> 5
2 -> 6
3 -> 7
4 -> 8

We can show that if there exists a solution with k assignments, it can be done by pairing a_i with a_{n - k + i} for all 1 ≤ i ≤ k:

1 2 5 | 6 7 | 8 9 10

1 -> 8
2 -> 9
5 -> 10

We can also show that if there exists a solution with k ≥ 1 assignments, there also exists a solution with k - 1 assignments. Thus we can binary search for the maximum k and use the greedy assignment to check whether it is in fact possible to have a certain amount of assignments in every step.

Runtime: O(n log n)

UPDATE (due to user interjay): From what we assume above, we can instead also greedily assign the element from the first half in increasing order to the first unassigned element in the second half. We can do so by maintaining a pointer to the element in the second half that comes after the one we assigned last. Runtime: O(n)