Problem
This problem was asked by Spotify.
You are the technical director of WSPT radio, serving listeners nationwide. For simplicity's sake, we can consider each listener to live along a horizontal line stretching from 0
(west) to 1000
(east).
Given a list of N
listeners, and a list of M
radio towers, each placed at various locations along this line, determine what the minimum broadcast range would have to be in order for each listener's home to be covered.
For example, suppose listeners = [1, 5, 11, 20]
, and towers = [4, 8, 15]
. In this case, the minimum range would be 5
, since that would be required for the tower at position 15
to reach the listener at position 20
.
Step 1: Framing
We need to approach such problems by first understanding the framing/setup of the problem. Unlike most problems, we are not dealing with location as points (2D) but a single index. We also know that people will live at most within a certain bound. Thus we can set up the solution with these bounds in mind.
The easy approach would be to go through the users. For every user iterate through the towers find the closest one, and calculate the range. The maximum from tower-user pair will be the minimum range we need to reach out to customers.
The problem with this approach is that will be O(n^2). Can we cut it down further?
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.