Алгоритм минимального расстояния

Question

Я читал здесь некоторое время, но это первый раз, когда я опубликовал, поэтому извиняюсь, если это не помечено правильно или что-то еще. Во всяком случае, я застрял в проблеме, которую я объясняю ниже.

Проблема заключается в том, чтобы устраивать n wifi-маршрутизаторы, чтобы свести к минимуму самое длинное расстояние между любым домом и ближайшим Wi-Fi маршрутизатором. Я могу предположить, что дома расположены в одномерном пространстве. Мне присваивается положение домов как расстояние от начальной точки, а позиции указаны в отсортированном порядке. Кроме того, я должен решить эту проблему в O (m log L), где m - количество домов, а L - максимальное положение, которое может быть задано.

Я попытался понять это, но ни один из алгоритмов, которые я придумал, не может решить его в требуемой сложности. Спасибо за любые подсказки о том, как я буду решать это.

Answer 1

Подсказка.

Легко написать функцию O(m), которая берет верхнюю границу по расстоянию и сообщает вам минимальное количество необходимых маршрутизаторов, чтобы убедиться, что ни один дом не находится выше этого расстояния от маршрутизатора.

Теперь найдите самое большое расстояние, которое использует не более n маршрутизаторов.