The input is a sequence of real numbers x1, x2, ..., x2n. We want to pair these numbers into n pairs. For the ith pair, (i = 1, 2, ..., n), let Si denote the sum of numbers in that pair. (For example if you pair x(2i−1) and x2i as the ith pair, Si = x(2i−1) + x2i). We want to pair these numbers so that Maxi[Si] is minimized. Design a greedy algorithm to solve this problem.
That's the question; my solution is to simply sort the numbers and pair the first-last elements and add-one/subtract-one index and repeat. The algorithm tries to optimize for each pair, so that makes it greedy. I'm just wondering if there's a linear time algorithm that will do this?
PS: This is not homework, but I understand this looks very much like it.
No. There can't be a linear time algo to get this done for you. The input numbers can be in any order so you cant get the pairing done right away with min Maxi[Si]. Your current solution is simple and good.
Suggestions to improve on the running time:
You can create a Binary tree out of the input numbers (this takes O(nlog(n)) time). Do inorder traversal of the tree and create pairs from the (first+i, last-i) elements (i from 0 to n/2)