**Key observation:** Each house should be covered by its nearest heater. The nearest heater to a house is either next right to it or next left to it, whichever is closer.

Algorithm:

- Sort heaters
`vector<int> hts`

by positions (O(N_{heater}logN_{heater})); - For each house
`h`

, use`std::lower_bound`

to find the nearest heater and update the overall min heater radius (O(logN_{heater}) for each house). Note- Next right heater position:
`i = lower_bound(hts.begin(), hts.end(), h)`

. - Next left heater position:
`--i`

for the iterator above .

- Next right heater position:

The overall time complexity is O((N_{house}+N_{heater})logN_{heater}).

```
int findRadius(vector<int>& houses, vector<int>& hts) {
sort(hts.begin(), hts.end()); int res = 0;
for (int h:houses) { // find nearest distance to heaters
auto i = lower_bound(hts.begin(), hts.end(), h); // next right heater
res = max(res, min(i!=hts.begin()? h-*(--i):INT_MAX, i!=hts.end()? *i - h:INT_MAX));
}
return res;
}
```