CodeChef:January2013 challenge: Salary problem solved

Solved the Salary problem on CodeChef January 2013 challenge. This is simply a very interesting problem. My trials with O(n^2log(n)) and O(n^2) came up with TLE (Time Limit Exceeded). The time available is just 1 second. I had to find an O(nlog(n)) or O(n) solution at least. Found an O(nlog(n)) solution. Realized that I had used one of the hints stated in multiple books: Algorithm Design Manual, Algorithms For Interviews. 

I will post the details after the challenge ends.

Update: the challenged ended 15th Jan and here's the official editorial: http://discuss.codechef.com/questions/5144/salary-editorial
My solution:
The hint that I used is to take a small example and solve it by hand. This is a pretty neat hint. Go ahead and try it.
Here't the set of comments from my code:

//Example: 33 100 1 9 40

//1 9 33 40 100       <- font="font" salaries="salaries" sorted="sorted">
//61 69 93 100 100    <- 60="60" add="add" all="all" font="font" to="to">
//68 76 100 107 100   <- 7="7" add="add" all="all" font="font" to="to">
//75 83 107 107 107   <- 7="7" add="add" all="all" font="font" to="to">
//99 107 107 131 131  <- 24="24" add="add" all="all" font="font" to="to">
//123 131 131 131 155 <- 24="24" font="font" nbsp="nbsp">(add 24 to all)
//147 155 155 155 155 <- 24="24" font="font" nbsp="nbsp">(add 24 to all)
//155 163 163 163 155 <- 8="8" font="font" nbsp="nbsp">(add 8 to all)
//163 171 171 163 163 <- 8="8" font="font"> (add 8 to all)
//171 179 171 171 171 <- 8="8" font="font"> (add 8 to all)
//179 179 179 179 179 <- 8="8" font="font"> (add 8 to all)
//Steps:
//1. Sort the list of salaries
//2. Add the diff of last 2 numbers 1 time
//3. Add the diff of n-1 and n-2 2 times
//4. Add the diff of n-2 and n-3 3 times
//5. Add the diff of n-3 and n-4 4 times
//6. ...
//n-1. Add the diff of n-(n-2) and n-(n-1) n-1 times

The editorial seems to have a simpler solution, but does not explain the process of arriving at the solution.