How to solve Listeners and Towers Problem: A complete Algorithm with code.
Problem Statement:
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
Explanation:
- Consider this first simple case where there is only one listener surrounded by a tower on each side.
a) As seen in the above picture, both tower A and tower B can cover the listener. Tower A is in 25 units range to the listener and tower B is in 20 units range.
b) The point to note here is there is no need for tower A. Because the listener is already covered the nearest tower B. Hence the maximum range of towers needed is 20 units.
2. Consider the other scenario which consists of several listeners and towers.
a) In the above picture, Listener 1 is covered by the nearest towers C and D. But, the distance between tower D and listener 1 is 8 units which is smaller than the distance between tower C and listener 1 which is 36 units. Hence tower D can cover the listener 1 and there is no need of tower C for the listener 1.
b) Similarly the listener 2 is covered by the nearest tower D which is 5 units away.
c) Listener 3 is covered by the nearest tower E which is 10 units away.
d) Listener 4 is covered by the nearest tower E which is 330 units away.
e) Here notice that, the towers A, B, C are not needed to cover any listener. Only the towers D and E are sufficient to cover all the listeners. Also, out of all, the listener 4 needs to be covered by the nearest tower E which is 330 units away and is the maximum range needed by the towers.
3. So, for every Listener, we should find the nearest Tower which is either on the right side or left side to it.
4. Calculate the distance between the Listener and its nearest Tower.
5. Finally find the maximum out of all those distances.
Algorithm:
Time complexity : O(m+n)
where m is the number of Listeners and n is the number of Towers.
a) We start traversing both Listener and Tower arrays at a time and stop once we reach the end of the Listener array.
b) For every value in the Listener array, we compare its distance between both left and right Towers.
c) We take the minimum value obtained from the above step and compare it with the maximum value found till now. If the current value is greater than the maximum value found till now, the replace the maximum value with the current value.
d) For simplicity we start with the left tower as the Integer.MIN_VALUE and right tower as the first element in the Tower array.
e) If we reach the end of the Tower array and the Listener array is still having elements, then we make the left tower as the last element in the Tower array and the right tower as the Integer.MAX_VALUE.
Code (JAVA)
