Sunday, 27 May 2012

Interviewstreet Unbxd CodeSprint Covering Cities : C++ code

Unbxd CodeSprint Covering Cities 

Unbxd Interview Question

Problem Statement

The country of Maryland is very strange. This country has only one very long straight road and all the cities are located on this road itself. Concretely you can assume the road to be X-axis and and cities as points. So each city i is located at some integer distance xi from the beginning of road.

To provide wireless connection in each of the city, it is required to install some antennas at some point on the road. All the antennas currently available have same coverage range say R, so if an antenna is installed at a point x then it covers all cities that lie in the closed interval [x-R, x+R].

Given the position of all cities on the road, your task is to find the minimum number of antennas required to cover all the cities.

Input Format
First line of input contains two space-separated integers, N and K. N is the number of cities and K is the coverage of any antenna as described in the problem statement. Next line contains a space-separated list of the positions of cities on road.

Output Format

Print an integer which is the required answer for this task.

Sample Input                                                                                
3 1
1 2 3
Sample Output
Sample Input
6 2
1 5 4 7 11 8
Sample Output
In the first sample testcase installing just one antenna at point 2 will have coverage of [2-1, 2+1] = [1, 3]. So this will cover all the cities. So just one antenna is sufficient in this case.
1 <= N,K <= 1000,000
0 <= x <= 1000,000
All cities are at integer distances.
Antennas can be installed at non-integer distances like 2.5.
Solution Code:

using namespace std;

int main()

int n,t;
int r= 2*t;
set<int> s;
set<int>::iterator it;
for(int i=0;i<n;i++)

int count =1;
int f=*it+r+1;




Time Complexity: O(n) 

// If you find this blog somewhat helpful, please share it.......&.......Keep visiting..:)


  1. Hi

    As far as i can tell, I had implemented the same algo, but I could only pass 3/5 testcases with my code.

    Code you tell me where I went wrong


  2. Hi Rohan,

    Your thinking is absolutely right. But you made a small mistake, "end = i + 2*k + 1" should be "end = i + 2*k" because once you have included i as the point to be covered by tower placed at i+k, the max point tower can cover is i+2k.


    Corrected Python code

    n, k = raw_input().split()
    k = float(k)
    arr = raw_input().split()
    s = set([])
    for a in arr:

    end = 0.0
    ans = 0
    for i in s:
    #print i, end
    if end < i:

    end = i + 2*k
    ans += 1
    print ans

    # If you liked the post, spread it to your friends
    # Keep visiting in future for other codes.


  3. ahhhh thanks :) keep up the good work on the site :)