Минимизируйте расстояние до самой дальней точки - PullRequest
Новая
       12

Минимизируйте расстояние до самой дальней точки

0 голосов
/ 02 мая 2019

Этот вопрос был задан в ходе собеседования.

Предположим, вы хотите переехать, и у вас есть набор удобств, к которым вы хотите иметь легкий доступ из своего нового дома.Вы нашли окрестности, которые вам нравятся, каждый из которых имеет ноль или более удобств.Как бы вы выбрали такой блок, чтобы жить так, чтобы минимальное расстояние до любого объекта в вашем списке было минимальным?

Например, скажем, ваш список содержит {school, grocery}, а блоки следующие:

1: ресторан, продуктовый магазин

2: кинотеатр

3: школа

4:

5: школа

Идеальным выбором был бы блок 2, так что расстояния до продуктового магазина и ближайшей школы - 1 каждый.Проживание в блоке 1 или 3 приведет к тому, что одно из расстояний будет равно нулю, а другое - 2.

Я пришел к наивному решению, как показано в псевдокоде ниже: 

max = minus infinity
min = plus infinity    

for r in requirements:
  for i in blocks:
    for j in blocks:
      if j.amenities contains r:
        max = maximum {max, dist(i, j)}
    if max < min:
      live_at = i

Если n - это количество блоков, сложность времени для этого алгоритма составляет O(n^2), если предположить, что список требований невелик по сравнению с n.Можем ли мы сделать лучше?

Этот вопрос кажется похожим, хотя ответ мне не ясен.Это относится к бумаге, и начинается с «Нарисуйте круг в центре, с», без каких-либо указаний на то, что c.

Ответы [ 2 ]

0 голосов
/ 02 мая 2019

Решение - это кратчайший поднабор блоков, который содержит все удобства.Обратите внимание, что удобство самого левого блока должно присутствовать только один раз;То же самое для правых.Блок, в котором нужно жить, будет прямо посередине.

Хорошо подходит метод двух указателей.

Иметь массив из k счетчиков, по одному на удобство в текущем окне, инициализировать егона все нули.Сделайте два указателя, left и right, в массив блоков;изначально оба указывают начало массива.Затем выполните шаги

  • Ускорение: передвиньте указатель right, считая удобства, которые он проходит, до тех пор, пока не встретятся все удобства.

  • Обрезать слева: перемещать указатель left, уменьшая счетчики соответственно, до тех пор, пока ни один из счетчиков не достигнет 0.У вас есть предварительное решение;запишите его.

  • В цикле

    • Advance left один раз, уменьшая значения соответствующих счетчиков.Некоторые из них поворачиваются к 0.
    • Обрежьте слева: продолжайте движение left до тех пор, пока другие счетчики не повернут к 0.
    • Продвигайте right, пока все счетчики не будут заполнены снова,Это еще одно предварительное решение, сохраняющее лучшее.
    • Продолжайте цикл, пока правый указатель больше не сможет продвигаться.

Предполагая, что любой данный блок неУ меня слишком много удобств, это будет работать в O(n) time, and O (k) `пространстве.

Доказательство правильности оставлено в качестве упражнения.

0 голосов
/ 02 мая 2019

Да, мы можем сделать это в O (n * k log n), где n - номер блока, а k - количество удобств

Список удобств невелик, поэтому создайте ArrayList за каждую услугу и складские позиции блоков, где есть эта услуга.

т.е. используя приведенный вами пример:

  • A ["restaurant"] = {1}
  • A ["бакалея"] = {1}
  • A ["кинотеатр"] = {2}
  • A ["школа"] = {3,5}

Так что теперь мы можем зациклить все блоки и использовать lower_bound (бинарный поиск) найти ближайший блок с необходимыми удобствами для каждого из необходимых удобств

Тогда просто выберите блок, который имеет минимальное расстояние до необходимых удобств.

...