I thought that the java sort method for a primative array used quick sort? since they will be sorting a nearly sorted array on almost every iteration, i think the runtime would be closer to O(N*M^2).

During each iteration, the array is sorted. result[0] is the slot with the smallest value, the next register that can take a customer. Initializing result to size n creates the a slot for each "register".

By any chance can someone explain this code please?
If we are using only result[0] (only the first element in the array) why initialize it with result[n] ?

The use of prevdist was a good catch!
The performance of the solution though doesn't look very good (O(N*M)).
One way to improve that would be by creating a map of distances using the input matrix (O(M)), and then use the map for accessing each distance when needed (O(1)). Total order of the solution that way would be O(N+M).

I loved the "catch" used in this solution. It made it very readable and look really simple.
The only thing I would do to improve would be to add a couple comment lines, briefing the idea (so no need to read through the code to first understand it)

Nice, very concise solution! It might only have performance issues for a big array of customers, as it would require O(N*M*log(M)) operations.
By not ordering the array you could get a O(N*M) solution.