Задача с собеседования в Zeta

Зима близко! Во время соревнования ваша первая задача - спроектировать стандартный обогреватель с фиксированным радиусом обогрева, чтобы обогреть все дома.
Каждый дом может быть обогрет, если он находится в пределах радиуса действия обогревателя.
Даны позиции домов и обогревателей на горизонтальной прямой. Верните минимальный стандартный радиус обогревателей, чтобы они могли покрыть все дома.

Обратите внимание, что все обогреватели соответствуют вашему стандарту радиуса, и радиус зоны нагрева будет одинаковым.

Пример 1:
Input: houses = [1,2,3], heaters = [2]
Output: 1
Explanation: Единственный обогреватель был установлен в позиции 2, и при использовании стандарта радиуса 1, все дома могут быть обогреты.

Пример 2:
Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
Explanation: Два обогревателя были установлены в позициях 1 и 4. Нам нужно использовать стандарт радиуса 1, тогда все дома можно будет обогреть.

Пример 3:
Input: houses = [1,5], heaters = [2]
Output: 3

Ограничения:
1 <= houses.length, heaters.length <= 3 * 10⁴
1 <= houses[i], heaters[i] <= 10⁹

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Итак, каждый обогреватель греет на фиксированное расстояние слева и справа, нужно найти минимальный радиус, чтобы все дома могли быть согреты.

Сортируем массивы houses и heaters, чтобы использовать метод двух указателей. Так как дома отсортированы, индекс ближайшего обогревателя для следующего дома не будет меньше, чем индекс для предыдущего дома => указатель по обогревателям движется монотонно вправо.

Указатели:
pos - индекс текущего кандидата в ближайший обогреватель
house - неявный указатель по домам в цикле for

Проходим по массиву houses, ища ближайший обогреватель для каждого дома:
Пока следующий обогреватель находится ближе к дому, чем текущий, или на том же расстоянии:
- сдвигаем pos вправо, переходя к следующему обогревателю.
Используем abs(), так как heaters[pos] может быть как слева (в таком случае heaters[pos] - house будет иметь отрицательное значение, а нам нужна положительная величина для корректного вычисления расстояния), так и справа от дома.

После выхода из цикла while:
heaters[pos] - ближайший обогреватель к текущему дому.
Вычисляем расстояние до него и обновляем res, беря максимальное расстояние до ближайшего обогревателя по всем домам - это и будет минимальный радиус, покрывающий самый удалённый от своего ближайшего обогревателя дом.

Сложность
O(n log n + m log m) - по времени (сортируем массивы; проход двумя указателями - за O(n + m), где n - кол-во домов, а m - кол-во обогревателей)
O(1) - по памяти (без учёта сортировки; храним некоторое кол-во переменных)

Код
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
houses.sort()
heaters.sort()

m = len(heaters)
res = 0
pos = 0

for house in houses:
while pos < m - 1 and abs(heaters[pos + 1] - house) <= abs(heaters[pos] - house):
pos += 1

res = max(res, abs(heaters[pos] - house))

return res

@algoses