Algorithm for re-arranging a sequence of weights

Nice greedy solution: for the first place take maximum number. For each next place take maximum from untaken numbers before that satisfy your condition. If you place all numbers - you have found a solution. Otherwise the solution doesn't exist, why - it's an exercise for you.

My proof: imagine a solution exists. Show, that my algorithm will find it. Let's a_1, ..., a_n - any solution. Let a_i - maximum element. Then a_i, a_{i-1}, ..., a_1, a_{i+1}, a_{i+2}, ..., a_n is a solution too, because a_1 <= a_i, a_1 + a_{i+1} <= a_i + a_{i+1}, so (a_i, a_{i+1}) is a good pair. Next, let a_1, ..., a_j is element according to my solution. Show, that a_{j+1} can be element, as my solution suppose to. Let a_i - maximum from a_{j+1}, .., a_n. Then a_1, ..., a_j, a_i, a_{i-1}, ..., a{j+1}, a_{i+1}, ..., a_n is a solution too. It shows that algo always find solution.

Big items can only be next to small items.

1. Sort the list
2. Cut in half
3. Reverse second half
4. Swap halves
5. Shuffle (take first item from each half, repeat)

Example: [1,3,8,4,2,4,1,7]

1. [1,1,2,3,4,4,7,8]
2. [1,1,2,3] [4,4,7,8]
3. [1,1,2,3] [8,7,4,4]
4. [8,7,4,4] [1,1,2,3]
5. [8,1,7,1,4,2,4,3]

I'm pretty sure you can't do better than this. If the business rule is violated anyway there is no solution. Prove/Counterexample left as an exercise ;-)

Edit: Take biggest item first!