Intv Q: Given m station and n house, output narest k stations for each house

Vote count:

0

There are m stations and n houses, (x,y) coordinates of each station and house are given, output nearest station for each house.

Later, the question was generalised to finding k nearest stations from each house.

My take: for every house, build a heap of distances(bottom up) to stations and then pop k. Do the same for all houses. O(n*(m+klogm));

for every house, build a order statistic tree to stations and then look for node wih rank and traverse the entire tree below that node. Do the same for all houses. O(n*(m+logm+k))

Are there any better alternatives to this?

asked 50 secs ago

claudius

135