11.8 Variant 3 (JAVA book) help

#1

I’m looking for help on Variant 3.

A number of apartment buildings are coming up on a new street. The postal service wants to place a single mailbox on street. Their objective is to minimize the total distance that residents have to walk to collect their mail each day. Different buildings may have different audience.

Simple solution to this seems like: finding building where either side number of residents would be same. However, this seems more complex then this as the heavy loaded building could be further away. Am I missing some point here. Please help

0 Likes

#2

It can be done in O(n) time, O(n) space using accumulated sums of people count. Lower space possible?

0 Likes