Heaters.java

package easy;

import java.util.Arrays;
/**
 * ClassName: Heaters.java
 * Author: chenyiAlone
 * Create Time: 2019/11/14 15:33
 * Description: No.475 Heaters
 *
 * Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.
 *
 * Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.
 *
 * So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.
 *
 * Note:
 *
 * Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
 * Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
 * As long as a house is in the heaters' warm radius range, it can be warmed.
 * All the heaters follow your radius standard and the warm radius will the same.
 *  
 *
 * Example 1:
 *
 * Input: [1,2,3],[2]
 * Output: 1
 * Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.
 *  
 *
 * Example 2:
 *
 * Input: [1,2,3,4],[1,4]
 * Output: 1
 * Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.
 *
 *
 */
public class Heaters {
    
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int ret = Integer.MAX_VALUE;
        int l = 0, r = Integer.MAX_VALUE;
        while (l <= r) {
            int mid = l + (r - l >>> 1);
            boolean can = true;
            for (int i = 0, index = 0; i < houses.length; i++) {
                while (index < heaters.length) {
                    if (Math.abs(houses[i] - heaters[index]) <= mid) break;
                    index++;
                }
                if (index == heaters.length) {
                    can = false;
                    break;
                }
            }
            if (can) {
                ret = Math.min(ret, mid);
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ret;
    }
    
}