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

1

Sample Input

6 2

1 5 4 7 11 8

Sample Output

2                         

Explanation

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.

Constraints

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:

#include<iostream>
#include<set>
using namespace std;

int main()
{

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

cin>>t;
s.insert(t);

}
it=s.begin();

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

while(s.lower_bound(f)!=s.end())
{
count++;
f=*(s.lower_bound(f))+r+1;

}

cout<<count;

}

Time Complexity: O(n) 


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