Note that a station with signal strength \(x\) will cover a segment on the number line of length \(x\). Thus we want to cover all the houses with \(M\) segments (including degenerate \(0\)-length segments) such that the sum of the segment lengths is minimized.

Sort \(X\) in non-decreasing order and draw a single segment from \(X_1\) to \(X_N\). This is obviously an answer for \(M = 1\). For greater \(M\), we could “break” this segment into \(M\) segments by erasing \(M-1\) sub-segments that lie between two neighboring houses. Obviously, we want to erase the longest of such sub-segments first, so we collect all \([X_{i+1} - X_i : 1 \le i \le N-1]\) into an array and sort it to find them.

[We could instead also think of it as “filling in” the \(N-M\) cheapest subsegments.]

The problem is thus solved in \(O(N \log N)\) due to sorting.