# Heaters

<https://leetcode.com/problems/heaters/description/>

> 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 separately, 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.

## Thoughts

刚开始以为给的是排好序了的，实际上并没有。

原来想单独分析houses之中和heaters之中的距离，然后再比较二者之间的距离，后失败。

实际上对每个house, 与它最近heater之间的距离就是它所需的最短辐射长度。我们要找针对所有houses的最短辐射长度，就取每个house的所需最短辐射长度最大值即可。

那么对给定的house如何找最近的heater? 把heaters排个序然后二分法即可。

## Code

```
class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int max = 0;
        for (int house : houses) {
            int start = 0, end = heaters.length;
            while (start < end) {
                int mid = start + (end - start) / 2;
                if (heaters[mid] < house) {
                    start = mid + 1;
                } else {
                    end = mid;
                }
            }
            int dist = start < heaters.length ? Math.abs(heaters[start] - house) : Integer.MAX_VALUE;
            dist = start > 0 ? Math.min(dist, Math.abs(heaters[start - 1] - house)) : dist;
            max = Math.max(max, dist);
        }

        return max;
    }
}
```

## Analysis

排序的时间复杂读是O(nlgn), 再加上找raius的O(mlgn).