Минимальное расстояние, при котором для каждого клиента есть хотя бы один продавец на заданном расстоянии.

Опубликовано: 20 Сентября, 2022

Даны N и M количество точек на прямой линии, обозначающие позиции покупателей и продавцов соответственно. Каждый продавец обслуживает всех клиентов, находящихся на расстоянии не более R от продавца. Задача состоит в том, чтобы найти минимальное R такое, что для каждого покупателя есть хотя бы один продавец на расстоянии, не превышающем R .

Примеры:

Input: N = 3, M = 2, customer[] = {-2, 2, 4}, vendor[] = {-3, 0}
Output: 4
Explanation: 4 is the minimum distance such that every customer is given service by at least one vendor. 

Input: N = 5, M = 3, customer [] = {1, 5, 10, 14, 17}, vendor[] = {4, 11, 15}
Output: 3
Explanation: 3 is the minimum distance such that every customer is given service by at least one vendor.

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

  • Возьмите два указателя: i для массива клиентов и j для массива поставщиков.
  • Начните перемещать указатель i и для каждого клиента я перемещаю индекс j , пока customer[i] > vendor[j] .
  • Теперь, когда поставщик[j] >= клиент[i] ,
    • поэтому проверьте правильное расстояние между ними, которое равно поставщику [j] — клиенту [i ], если j < m .
    • Проверьте левое расстояние, т.е. покупатель[i] – продавец[j – 1] , если j > 0 .
    • Найдите минимум из этих двух, т.е. кратчайший диапазон, которым может быть охвачен клиент[i] ; достигается путем сравнения расстояния между этими двумя соседними поставщиками.
    • Затем максимально максимизируйте это свойство, чтобы получить ответ.
  • Наконец, выведите найденный ответ.

Ниже приведена реализация описанного выше подхода.


Сложность времени: О (Н + М)
Вспомогательное пространство: О(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ