供暖器
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
示例:
输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
思路
解法一：
需要求得最小加热半径 ans，使得所有的 houses[i 均被覆盖。
在以 ans为分割点的数轴上具有「二段性」：
- 数值小于 ans的半径无法覆盖所有的房子；
- 数值大于等于 ans的半径可以覆盖所有房子
先对 houses和 heaters进行排序，使用 i指向当前处理到的 houses[i]；j 指向可能覆盖到 houses[i]h的最小下标 heaters[j]；x 代表当前需要 check 的半径。
当且仅当 heaters[j]+x<houses[i] 时，houses[i] 必然不能被 heaters[j] 所覆盖，此时让 j 自增。
找到合适的 j之后，再检查 heaters[j]−x<=houses[i]<=heaters[j]+x是否满足，即可知道 houses[i]的覆盖情况。
from typing import List
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
houses.sort()
heaters.sort()
l, r = 0, max(houses[-1], heaters[-1])
while l < r:
mid = l + r >> 1
if self.check(houses, heaters, mid):
r = mid
else:
l = mid + 1
return r
def check(self, houses, heaters, x):
n = len(houses)
m = len(heaters)
j = 0
for i in range(n):
while j < m and houses[i] > heaters[j] + x:
j += 1
if j < m and heaters[j] - x <= houses[i] and houses[i] <= heaters[j] + x:
continue
return False
return True