Minimum Heater Radius for All Houses
Given the positions of houses and heaters on a horizontal line, determine the minimum common heating radius needed to warm every house.
A heater at position x with radius r warms every house from x - r through x + r, inclusive. All heaters must use the same radius.
Method Signature
int findRadius(List<Integer> houses, List<Integer> heaters)
houses contains the positions of the houses.heaters contains the positions of the heaters.- Returns the smallest non-negative radius that allows the heaters to warm every house.
Constraints
1 ≤ houses.size() ≤ 25,0001 ≤ heaters.size() ≤ 25,0000 ≤ houses.get(i) ≤ 1,000,000,0000 ≤ heaters.get(i) ≤ 1,000,000,000- House and heater positions may contain duplicates.
Examples
Example 1
findRadius(houses = [1, 5, 9], heaters = [2, 8])
Output: 3
The house at position 5 is three units from its nearest heater. Therefore, the minimum common radius is 3.
Example 2
findRadius(houses = [0, 4, 10, 14], heaters = [1, 12])
Output: 3
A radius of 3 covers every house. Any smaller radius would leave the house at position 4 uncovered.