LC475 Heaters

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        # time O(N*M) spaceO(1)
        # main idea:  create two extreme heaters at two end, record each house's min neighbour distance, and get the max
        heaters.sort()
        houses.sort()
        heaters =  [float('-inf')] + heaters+[float('inf')]
        res, idx = 0,0
        for house in houses:
            while house > heaters[idx+1]:
                idx += 1
            distance = min(house-heaters[idx],heaters[idx+1]-house)
            res = max(res,distance)
        return res