475. Heaters

T: O((m+n)logm)
S: O(1)

class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int res = 0;
        for (int house : houses) {
            int radius = findClosetHeater(house, heaters);
            res = Math.max(res, radius);
        }
        return res;
    }
    private int findClosetHeater(int house, int[] heaters) {
        int start = 0;
        int end = heaters.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start)/2;
            // heater. house
            if (heaters[mid] < house) {
                start = mid;
            } else {
                end = mid;
            }
        }
        int startDist = Math.abs(heaters[start] - house);
        int endDist = Math.abs(heaters[end] - house);
        return Math.min(startDist, endDist);
    }
}

/*

n
find each house's minRadius, for all houses: get max Radius for all houses

logm
how find house's minRadius?

mlogm
sort heaters, find the most closet heater to house, return the minRadius (heater to house min dist)

T: O((m+n)logm)
S: O(1)
*/