## 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.**Problem Statement**

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

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);

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;

}

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;

}

__O(n)__

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

Hi

ReplyDeleteAs 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

https://gist.github.com/2843026

Thanks

Hi Rohan,

ReplyDeleteYour 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.

<-----i----->

Corrected Python code

---------------------

n, k = raw_input().split()

k = float(k)

arr = raw_input().split()

s = set([])

for a in arr:

s.add(float(a))

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.

regards,

Sachin

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

ReplyDelete