Skip to interview prep
Apexed

342. Houses lie at points along a straight road. A tower covers every house within 4 miles. Place the fewest towers so every house is covered.

MediumGreedy algorithms

Technical
Show model answer

Sort the houses. Take the westernmost uncovered house at position x and put a tower at x + 4, the farthest east position that still covers it. Skip every house up to x + 8, then repeat from the next uncovered house. Sorting costs O(n log n) and the sweep is O(n), with O(1) extra space.

Any valid solution must place some tower within 4 miles of the first uncovered house; moving that tower to x + 4 covers at least the same houses to the east, so greedy stays ahead. The same pattern solves 'minimum arrows to burst balloons' and 'minimum points to stab all intervals': sort by right end and place a point at the earliest right end not yet stabbed.

Houses lie at points along a straight road. A tower covers every house within 4 miles. Place the fewest towers so every house is covered. — Data structures & al