Winter has arrived. Your task is to design heaters with a fixed heating radius to warm all the houses.
Every house within the heating radius of a heater can receive heat.
Given the positions of the houses houses and heaters heaters on a horizontal line, find and return the minimum heating radius that covers every house.
Note: All heaters use the same radius specified by you, so their heating radii are identical.
Example 1:
Input: houses = [1,2,3], heaters = [2]
Output: 1
Explanation: There is one heater at position 2. If we set the heating radius to 1, every house can be heated.
Example 2:
Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
Explanation: There are two heaters at positions 1 and 4. We need a heating radius of 1 to heat every house.
Example 3:
Input:houses = [1,5], heaters = [2]
Output:3
Constraints:
1 <= houses.length, heaters.length <= 3 * 1041 <= houses[i], heaters[i] <= 109
Solution#
impl Solution {
pub fn find_radius(mut houses: Vec<i32>, mut heaters: Vec<i32>) -> i32 {
houses.sort_unstable();
heaters.sort_unstable();
let mut res = 0;
let mut cur = 0;
for house in houses {
while cur < heaters.len() - 1 &&
(heaters[cur + 1] - house).abs() <= (heaters[cur] - house).abs() {
cur += 1;
}
res = res.max((heaters[cur] - house).abs())
}
res
}
}