475. Heaters

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);

        // 覆盖所有房屋的最小的加热半径即为每个房屋左右相对小的半径中的最大值
        int minRadiusForAllHouse = 0, minRadiusForSingleHouse = 0;

        int j = 0;
        for (int houseLocation : houses) {
            // 找到房子右侧最近的供暖器
            while (j < heaters.length && heaters[j] < houseLocation) {
                j++;
            }

            // 跳出时存在两种情况
            // 一是 j = heaters.length, 此时说明当前房子右侧没有供暖器，最近的供暖器在左侧，只能通过左侧取暖
            // 一是 heaters[j] >= house, 当前供暖器就是右侧最近的

            if (j == heaters.length) {
                minRadiusForSingleHouse = houseLocation - heaters[j - 1];
            } else if (j == 0) {
                // 如果 j 没有移动过，说明没有进入上面的 while 循环，即首次比较时该供暖器就位于房子的位置或者房子右侧，此时当前房子最近的供暖器就是当前 j 所指向的供暖器
                minRadiusForSingleHouse = heaters[j] - houseLocation;
            } else {
                // 右侧的供暖器没有位于两端，说明房子左侧和右侧都有供暖器，此时找出最近的供暖器
                minRadiusForSingleHouse = Math.min(houseLocation - heaters[j - 1], heaters[j] - houseLocation);
            }

            // 此处取 max, 因为需要保证所有房屋都能取暖
            minRadiusForAllHouse = Math.max(minRadiusForAllHouse, minRadiusForSingleHouse);
        }

        return minRadiusForAllHouse;
    }
}

References

475. Heaters