The basic idea is:
- For each house, I find the left-nearest and right-nearest heaters and calculate two distances;
- Find the minimum of the two distances for all houses;
- Find the maximum of all the minimums in step2.
Several things need to be considered very carefully:
- Heaters has to be sorted;
- Two border situation: house is larger than any element in heaters, or house is smaller than any element in heaters;
- Understand the return index of bisect(), and manipulate carefully.
FYI: Link to bisect(): disect()
class Solution(object): def findRadius(self, houses, heaters): import bisect heaters.sort() rs = 0 for i in houses: index = bisect.bisect(heaters, i) leftVal = 10 ** 9 if index == 0 else i-heaters[index-1] rightVal = 10 ** 9 if index == len(heaters) else heaters[index] - i rs = max(rs, min(leftVal, rightVal)) return rs