供暖期-分治

题目

在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

示例

输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1

算法

二分搜索合适的半径：
半径最小值为0，最大值为供暖器和房子的最远位置
小于最优解的半径一定不能供暖所有房子
大于最优解的半径一定可以供暖所有房子
所以可以二分查找到最优解
二分查找时，当满足供暖要求时，使high = mid-1，因为左边的半径都不满足，右边的半径都满足，所以，high最后会停在从右向左的第一个不满足供暖要求的点。
双指针判断是否满足供暖要求：
如果一个房子A在一个房子B前面，那么可以给A供暖的供暖期间一定在能给B供暖的供暖期前面，或者是同一个供暖器
i指向房子，遍历每一个房子，寻找他的供暖器，如果有一个房子找不到供暖器，则不满足供暖要求，否则满足供暖要求。

代码

class Solution {
    public boolean check(int radius, int[] houses, int[] heaters) {
        int j = 0;
        for (int i = 0; i < houses.length; i++) {
            while (j < heaters.length &&  Math.abs(houses[i] - heaters[j]) > radius) {
                j++;
            }
            if (j == heaters.length) {
                return false;
            }
        }
        return true;
    }
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int left = 0;
        int right = Math.max(houses[houses.length-1], heaters[heaters.length-1]);
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (check(mid, houses, heaters)) {
                right = mid - 1;
            } else {
                left  = mid + 1;
            }   
        }
        return right + 1;
    }
}