Minimum Sum of All Travel Times

I found a puzzle online on interviewStreet and tried to solve it as follows:

There is an infinite integer grid at which N people have their houses on. They decide to unite at a common meeting place, which is someone's house. From any given cell, all 8 adjacent cells are reachable in 1 unit of time. eg: (x,y) can be reached from (x-1,y+1) in a single unit of time. Find a common meeting place which minimizes the sum of the travel times of all the persons.

I thought first about writing a solution in n² complexity in time, but the constraints are

1<=N<=10^5 and The absolute value of each co-ordinate in the input will be atmost 10^9

So, I changed my first approach and instead of looking at the problem with the distances and travel times, I looked at the different houses as different bodies with different weights. And instead of calculating all the distances, I look for the center of gravity of the group of bodies.

Here's the code of my "solve" function, vectorToTreat is an lengthX2 table storing all the data about the points on the grid and resul is the number to print to stdout:

long long solve(long long** vectorToTreat, int length){
    long long resul = 0;
    int i;
    long long x=0;
    long long y=0;
    int tmpCur=-1;
    long long tmp=-1;
    for(i=0;i<length;i++){
        x+=vectorToTreat[i][0];
        y+=vectorToTreat[i][1];
    }
    x=x/length;
    y=y/length;
    tmp = max(absol(vectorToTreat[0][0]-x),absol(vectorToTreat[0][1]-y));
    tmpCur = 0;
    for(i=1;i<length;i++){
        if(max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y))<tmp){
            tmp = max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y));
            tmpCur = i;
        }
    }
    for(i=0;i<length;i++){
        if(i!=tmpCur)

If you think a bit about the distance function you get as travel time between (x1,y1) and (x2,y2)

def dist( (x1,y1), (x2,y2)):
    dx = abs(x2-x1)
    dy = abs(y2-y1)
    return max(dx, dy)

You can see that if you make a sketch on a paper with a grid.

So you only have to iterate over each house, sum up the travel times of the others and take the house with the minum sum.

The full solution is

houses = [ (7,4), (1,1), (3,2), (-3, 2), (2,7), (8, 3), (10, 9) ]

def dist( (x1, y1), (x2, y2)):
    dx = abs(x1-x2)
    dy = abs(y1-y2)
    return max(dx, dy)

def summed_time_to(p0, houses):
    return sum(dist(p0, p1) for p1 in houses)

distances = [ (summed_time_to(p, houses), i) for i, p in enumerate(houses) ]
distances.sort()

min_dist = distances[0][0]

print "best houses are:"
for d, i in distances:
    if d==min_dist:
        print i, "at", houses[i]

answered 2011-08-24T14:38:16.683

Minimum Sum of All Travel Times

1 Answer

Your Answer