Minimum Distance Algorithm

Question

I read here for a while, but this is the first time I published, so I apologize if this is not marked correctly or something else. Anyway, I'm stuck in a problem that I explain below.

In this task, my task is to organize n wifi routers to minimize the longest distance between any home and the nearest Wi-Fi router. I can assume that the houses are located in one-dimensional space. I am assigned the position of the houses as the distance from the starting point, and the positions are indicated in sorted order. In addition, I have to solve this problem in O (m log L), where m is the number of houses and L is the maximum position that can be specified.

I tried to figure it out, but none of the algorithms that I came up with can solve it in the required complexity. Thanks for any tips on how I will solve this.

Answer 1

Here is a hint.

It is easy to write an O(m) function that takes the upper limit of the distance and tells you the minimum number of routers needed to make sure that no home is above this distance from the router.

Now find the maximum distance that no more than n routers use.