Let the given points be x_i, i = 1, 2, ..., n. For any point x on the
line, let
f(x) = sum_{i=1}^n | x - x_i |.
Then, from calculus, we know that f(x) attains its extreme point at a
point where its derivative is zero or undefined. Because of the
absolute value signs, the derivative is undefined at the x_i. Since
f(x) is linear between adjacent x_i, it suffices to check only f(x_i)
in search of the minimum. As you proceed toward the right from the
leftmost x_i, the function decreases as long as there are more x_i to
the right of x than to the left, and increases whenever there are more
x_i to the left than to the right. Hence, if N is odd, the minimum
occurs at the median of the {x_i}. If N is even, the post office can
be anywhere in the center interval.Dave On Jun 23, 7:18 am, amit <[email protected]> wrote: > There are N points on a LINE. U neeed to place a post office such that > its total distance from each of the N points is minimised. > > The post office need not necessarily be on one of the N Points. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
