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

Задача с собеседования в 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