I have a restroom that I need to place at some point. I want the restroom's placement to minimize the total distance people have to travel to get there.

So I have x apartments, and each house has n people living in each apartment, so the apartments would be like a_1, a_2, a_3, ... a_x and the number of people in a_1 would be n_1, a_2 would be n_2, etc. No two apartments can be in the same space and each apartment has a positive number of people.

So I know the distance between an apartment a_1 and the proposed bathroom, placed at a, would be |a_1 - a|.

MY WORKING:

I defined a cost function, C(a) = SUM[from i = 1 to x] (n_i)|a_i - a|. I want to find the location a that minimizes this cost function, given two arrays - one for the location of the apartments and one for the number of people in each apartment. I want my algorithm to be in O(n) time.

I was thinking of representing this as a graph and using MSTs or Djikstra's but that would not meet the O(n) runtime. Clearly, there must be something I can do without graphs, but I am unsure.

CodePudding user response：

My understanding of your problem: You have a once dimensional line with points a1,...,an. Each point has a value n1,....n, and you need to pick a point a that minimises the cost function

SUM[from i = 1 to x] (n_i)|a_i - a|.

Lets assume a1...an is sorted.

Our strategy will be a sweep from left to right, calculating possible a on the way.

Things we will keep track of:

total_n : the total number of people left_n : the number of people living to the left or at our current position
right_n : the number of people living to the right of our current position
a: our current postition

Calculate:

C(a)
left_n = n1
right_n = total_n - left_n

Now we consider what happens to the sum if we move our restroom to the right 1 step. The people on the left get 1 step further away, but the people on the right get 1 step closer.

We can say that C(a 1) = C(a) left_n -right_n

If the range an-a1 is fairly small, we can use this and just step through the range using this formula to update the sum. Note that when this sum starts increasing we have gone too far and can safely stop.

However, if the apartments are very far apart we cannot step 1 by 1 unit. We nned instead to step apartment by apartment. Not

C(a[i]) = C(a[i-1])   left_n*(a[i]-a[a-1]) - right_n*(a[i]-a[i-1])

If at any point C(a[i]) > C(a[i-1]) we know that the correct position of the restroom is somewhere between i and i-1.

We can calculate that position, lets call it x.

The sum at x is C(a[i-1]) left_n*(x-a[i-1]) - right_n*(x-a[i-1]) and we want to minimize this. Note that everything but x is know values.

We can simplify to

f(x) = C(a[i-1])   left_n*x-left_n*a[i-1]) - right_n*x-left_n*a[i-1])

Constant terms cannot affect this sum so we are actually looking to minize

f(x) = x*(left_n-right_n)

We see that if left_n < right_n we want the restroom to be at i 1, but if left_n > right_n we want the restroom to be at i.

We need to at most do this calculation at each apartment, so the running time is O(n).