Heaters – Python 3 ( Week 14 – 07)

 class Solution:
    """
    @param houses: positions of houses
    @param heaters: positions of heaters
    @return: the minimum radius standard of heaters
    """
    def findRadius(self, houses, heaters):
        # Write your code here
        houses = sorted(houses)
        heaters = sorted(heaters)
        start = 0
        end = houses[-1] - houses[0]
        
        # O(log(end))*O(n+m)
        while start + 1 < end:
            mid = start + (end - start) // 2
            if self.check(mid, houses, heaters):
                end = mid
            else:
                start = mid
        if self.check(start, houses, heaters):
            return start
        return end
        
    def check(self, mid, houses, heaters):
        now_heater = 0
        for i  in range(len(houses)):
            while now_heater < len(heaters) and abs(houses[i] - heaters[now_heater]) > mid:
                now_heater += 1
            if now_heater == len(heaters):
                return False
        return True