Find One Heater Radius That Reaches Every House

# Find One Heater Radius That Reaches Every House The positions of `houses` and `heaters` lie on a horizontal line. Every heater uses the same nonnegative warming radius. A house is warmed when its distance from at least one heater is at most that radius. Return the smallest common radius that warms every house. Heater positions are fixed. ### Interface `class Solution { public: int findRadius(vector<int>& houses, vector<int>& heaters); };` ### Example 1 ```text Input: houses = [1,4,8], heaters = [2,9] Output: 2 ``` The house at 4 is distance 2 from its nearest heater. Radius 2 also covers the houses at 1 and 8, while any smaller radius misses the house at 4. ### Example 2 ```text Input: houses = [1,11], heaters = [4,8] Output: 3 ``` The two houses are each distance 3 from their nearest heater, so the minimum common radius is 3. ### Constraints - `1 <= houses.length, heaters.length <= 30000`. - `1 <= houses[i], heaters[i] <= 1000000000`. ### What a Strong Answer Covers - One shared radius rather than a separate radius for each heater. - Houses beyond the leftmost or rightmost heater and houses at heater positions. - Unsorted or repeated positions without adding a uniqueness assumption. - A minimality proof and resource bounds for the full arrays. ```hint The limiting house For one particular house, what is the smallest radius that could possibly warm it? ```