## Algorithm

Problem Name: 475. Heaters

Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.

Every house can be warmed, as long as the house is within the heater's warm radius range.

Given the positions of `houses` and `heaters` on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.

Notice that all the `heaters` follow your radius standard, and the warm radius will the same.

Example 1:

```Input: houses = [1,2,3], heaters = [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: houses = [1,2,3,4], heaters = [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.
```

Example 3:

```Input: houses = [1,5], heaters = [2]
Output: 3
```

Constraints:

• `1 <= houses.length, heaters.length <= 3 * 104`
• `1 <= houses[i], heaters[i] <= 109`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
int cmp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int r = 0, k;
int i, j;

qsort(houses, housesSize, sizeof(int), cmp);

j = 0;
for (i = 0; i < housesSize; i ++) {
while (j < heatersSize - 1 &&
abs(heaters[j + 1] - houses[i]) <= abs(heaters[j] - houses[i])) {
j ++;
}
k = abs(heaters[j] - houses[i]);
if (r < k) r = k;
}
return r;
}
``````
Copy The Code &

Input

cmd
houses = [1,2,3], heaters = [2]

Output

cmd
1

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findRadius = function(houses, heaters) {
heaters.sort((a, b) => a - b)
return Math.max(...houses.map(h => findMinDistance(h, heaters)))
}

const findMinDistance = (house, heaters) => {
let left = 0
let right = heaters.length - 1
while (left <= right) {
const mid = left + ((right - left) >> 1)
if (heaters[mid] <= house && house <= heaters[mid + 1]) {
return Math.min(house - heaters[mid], heaters[mid + 1] - house)
} else if (heaters[mid] <= house) {
left = mid + 1
} else {
right = mid - 1
}
}
if (left === 0) return heaters[0] - house
if (left === heaters.length) return house - heaters[heaters.length - 1]
}
``````
Copy The Code &

Input

cmd
houses = [1,2,3], heaters = [2]

Output

cmd
1

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
heaters.sort()
r = 0
for h in houses:
ind = bisect.bisect_left(heaters, h)
if ind == len(heaters):
r = max(r, h - heaters[-1])
elif ind == 0:
r = max(r, heaters[0] - h)
else:
r = max(r, min(heaters[ind] - h, h - heaters[ind - 1]))
return r
``````
Copy The Code &

Input

cmd
houses = [1,2,3,4], heaters = [1,4]

Output

cmd
1

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Linq;

namespace LeetCode
{
public class _0475_Heaters
{
public int FindRadius(int[] houses, int[] heaters)
{
Array.Sort(houses);
Array.Sort(heaters);

var distances = new int[houses.Length];
for (int i = 0; i < houses.Length; i++)
distances[i] = int.MaxValue;

for (int i = 0, h = 0; i < houses.Length && h < heaters.Length;)
{
if (houses[i] <= heaters[h])
{
distances[i] = heaters[h] - houses[i];
i++;
}
else
h++;
}

for (int i = houses.Length - 1, h = heaters.Length - 1; i >= 0 && h >= 0;)
{
if (houses[i] >= heaters[h])
{
distances[i] = Math.Min(distances[i], houses[i] - heaters[h]);
i--;
}
else
h--;
}

return distances.Max();
}
}
}
``````
Copy The Code &

Input

cmd
houses = [1,2,3,4], heaters = [1,4]

Output

cmd
1