Heater#

Winter is here. Your task is to design a heater with a fixed heating radius to heat all the houses.
Each house within the heating radius of the heater can receive heating.
Now, given the positions of houses houses and heaters heaters located on a horizontal line, please find and return the minimum heating radius that can cover all the houses.
Note: All heaters follow your radius standard, and the heating radius is the same.

Example#

Solution#

/**
 * @param {number[]} houses
 * @param {number[]} heaters
 * @return {number}
 */
var findRadius = function(houses, heaters) {
    houses.sort((a, b) => a - b);
    heaters.sort((a, b) => a - b);
    let max = -Infinity;
    houses.forEach(house => {
        let left = 0, right = heaters.length - 1;
        let tmp = Infinity;
        while(left <= right){
            let mid = (left + right) >> 1;
            if(heaters[mid] === house){
                tmp = 0;
                break;
            }else if(house < heaters[mid]){ // Heater is to the right of the house
                tmp = Math.min(tmp, heaters[mid] - house);
                right = mid - 1;
            }else{ // Heater is to the left of the house
                tmp = Math.min(tmp, house - heaters[mid]);
                left = mid + 1;
            }
        }
        max = Math.max(max, tmp);
    })
    return max;
};

Idea#

The overall idea is to traverse the houses, find the nearest heater to each house, and then compare all the nearest heaters to the houses to find the longest radius of the heater, so that the heater with a fixed heating radius can provide heating to all the houses. First, sort the positions of houses and heaters. If the data in the problem is not in order, sort it. Define a maximum value variable, traverse all house positions. Use binary search here. Take 0 for the left and heater number - 1 for the right as the index value. When left is less than right, run the loop. Get mid as the middle value of the two pointers, and Bitwise right shift by one is equivalent to divide by 2 and take the integer. If the position of the heater is the same as the position of the house, then the shortest distance is 0, return and end the loop. If the heater is to the right of the house, then take tmp as the minimum value compared to the distance between the heater and the house at this time, and set the right pointer to mid - 1. You can take an example. 0 1 2 3 4 5 6 are all heaters. Suppose when the traversed house is at position 2, the first time the binary search gets the heater position is 3, then the right pointer is pointed from 6 to 2, and so on. Similarly, if the heater is to the left of the house, then take tmp as the minimum value compared to the distance between the heater and the house at this time, and set the left pointer to mid + 1. After the loop ends, the distance to the nearest heater to the current house belongs to tmp After that, get the maximum value between max and the closest distance of the current house to the heater, and after the outer loop ends, you can get the longest range of the nearest heater of all the houses. The heating radius, finally return this value.

Daily Topic#

Reference#