A mailbox placement algorithm to minimize the total distance residents travel to receive mail
Suppose the entrance is defined as an array of building objects, where each building has several residents at a distance from the beginning of the street.
Total distance = SUM (distance [i] * #residents [i])
I found two questions here that are similar but have slightly different requirements:
-
Minimizing a weighted sum : The solution to this question is finding the smallest path that crosses all points. Here I am looking for the minimum sum of the total distances from each building to the location where the mailbox is located.
-
Minimum total distance from locations : It uses 2D coordinates and more importantly, the solution does not take into account the weight (number of inhabitants) at each location, etc.
I've seen this issue while reading Elements of Programming Interviews (really good book, BTW) and it is listed as a variant of the quickselect algorithm. Given that the median is the point that minimizes the sum of the distances, it looks like the solution would involve a quick pick to find the building at the "median" street position at O (N).
But I can't figure out how to account for residents in each building and maintain a linear solution.
source to share
We can use delta to determine direction. I will explain what I mean. Since this is about choosing the location of a mailbox in one of the buildings (that is, not between two buildings):
Select one of the buildings as the pivot (potential mailbox location). Divide the buildings according to their position relative to the bar. While subdividing, keep a record of the nearest building on each side of the bar, as well as (1) the total number of inhabitants on each side of the bar, and (2) f(side, pivot)
representing the total of each building, the distance from the pivot multiplied by the number of inhabitants in that building.
We now have:
L pivot R
To determine if the selection can be improved for our selection, try each of the nearby buildings we recorded earlier:
If we moved our selection one building to the left, how would the results change? Let's name the nearest building to the left build_l
and to the right - build_r
. So the new results driving our selection in one building on the left will be:
Left-hand side:
f(L, pivot)
- distance(build_l, pivot) * num_residents(build_l)
Right side:
f(R, pivot)
// we saved this earlier
+ total_residents(R) * distance(pivot, build_l)
+ num_residents(pivot) * distance(pivot, build_l)
Perform a similar calculation to move the selection of one building to the right to see what gives the lower total. Then pick the side with the building that will give the upgrade and expand it recursively in the same way quickselect until you find the optimal result. For the other side, we keep track of the total number of inhabitants and the total result for f
so far, which we can update with new additions as we go.
source to share