641. The Smallest Radius That Warms Every House
Houses and heaters stand at given positions on a line. Every heater is set to the SAME radius
r, and a house is warm when some heater is within r of it.
Print the smallest r that warms every house.
houses 1 2 3, heaters 2 -> 1
houses 1 2 3 4, heaters 1 4 -> 1
houses 1 5, heaters 2 -> 3
## The answer is a maximum of minimums
Each house needs its OWN nearest heater, and the radius has to satisfy the worst-off house:
r = max over houses of ( min over heaters of |house - heater| )
Reading it in that order matters. A common misreading takes the minimum of the maxima, or the distance between the extreme positions, and both are wrong.
## Why sorting turns it linear
Done directly, this is O(H * T). Sort both lists and the inner minimum becomes a sweep: as
the houses advance rightwards, the best heater for them also only advances rightwards.
sort houses, sort heaters
j = 0
for each house h in order:
while j+1 < T and |heater[j+1] - h| <= |heater[j] - h|: j += 1
r = max(r, |heater[j] - h|)
## Why the heater pointer never goes back
The houses are visited in increasing order. If heater j+1 is at least as good as heater j
for the current house, it stays at least as good for every house further right, because moving
right can only reduce the distance to a heater on the right and increase it to one on the left.
So j never needs to retreat, and the whole sweep is linear after the sorts.
## The comparison must be non-strict
Advance while the next heater is at least as good, using <=, not strictly better. With <
the pointer can stall on a tie and then lag behind for every later house.
## Boundaries
A house sitting exactly on a heater needs radius 0, so an answer of 0 is possible and must not be excluded by starting the running maximum at 1.
A single heater far from everything gives a large radius: houses 1 100 with a heater at 50
needs 50.
## Overflow
Positions run to 10^9 in both directions, so a house and a heater at opposite extremes sit
2 * 10^9 apart. Check that against the limit rather than assuming: a signed 32 bit integer
holds up to 2147483647, so 2000000000 FITS, with about seven percent to spare. This
problem has no overflow.
The answer is a radius, so it is a distance and never negative, which means the
-2147483648 end of the range never comes into it at all.
## Cost
Time O(H log H + T log T) for the sorts. Space O(1) beyond the input.
Constraints - `1 ≤ H, T ≤ 200000` - `-10^9 ≤ each position ≤ 10^9` - positions may repeat and arrive in any order
Input
The first line contains two integers H and T, the number of houses and heaters.
The second line contains H integers, the house positions.
The third line contains T integers, the heater positions.
Output
Print one integer, the smallest radius that warms every house.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.