Hackerland Radio Transmitters

출처 : 해커 랭크

난이도 : 중간

 

Hackerland is a one-dimensional city with houses aligned at integral locations along a road. The Mayor wants to install radio transmitters on the roofs of the city's houses. Each transmitter has a fixed range meaning it can transmit a signal to all houses within that number of units distance away.

Given a map of Hackerland and the transmission range, determine the minimum number of transmitters so that every house is within range of at least one transmitter. Each transmitter must be installed on top of an existing house.

Example

x = [1,2,3,5,9]

k = 1

3 antennae at houses 2 and 5 and 9 provide complete coverage. There is no house at location 7 to cover both 5 and 9. Ranges of coverage, are [1,2,3], [5], and [9].

Function Description

Complete the hackerlandRadioTransmitters function in the editor below.

hackerlandRadioTransmitters has the following parameter(s):

• int x[n]: the locations of houses
• int k: the effective range of a transmitter

Returns

• int: the minimum number of transmitters to install

Input Format

The first line contains two space-separated integers n and k, the number of houses in Hackerland and the range of each transmitter.
The second line contains n space-separated integers describing the respective locations of each house x[i].

Constraints

• 1 ≤ n,k ≤10^5
• 1 ≤ x[i] ≤ 10^5
• There may be more than one house at the same location.

Subtasks

• 1≤ n ≤ 1000 for 50% of the maximum score.

Output Format

Print a single integer denoting the minimum number of transmitters needed to cover all of the houses.

Sample Input 0

STDIN       Function
-----       --------
5 1         x[] size n = 5, k = 1
1 2 3 4 5   x = [1, 2, 3, 4, 5]  

Sample Output 0

2

Explanation 0

The diagram below depicts our map of Hackerland:

We can cover the entire city by installing  transmitters on houses at locations 2 and 4.

Sample Input 1

8 2
7 2 4 6 5 9 12 11 

Sample Output 1

3

Explanation 1

The diagram below depicts our map of Hackerland:

We can cover the entire city by installing  transmitters on houses at locations 4, 9, and 12.

 

 

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

 

문제 해독

라디오 안테나를 최소한으로 설치하여 모든 가구에 안테나 사용을 제공하는 문제

 

문제접근

시작 가구에 전파를 제공할 수 있는 다음 집을 구한 다음 해당 가구에 설치했을시에 영향을 미치는 다음 가구까지 스킵하여 다음 가구를 시작가구로 지정하여 반복 탐색한다. 가구의 수가 바뀐 횟수가 안테나를 설치한 횟수가 된다.

 

알고리즘

 - 정렬

 

public static int hackerlandRadioTransmitters(List<int> x, int k)
    {
        x.Sort();

        int index = 0;
        int result = 0;
        
        while(index < x.Count)
        {
            int start = x[index];
        
            while(index < x.Count && x[index] <= start + k)
                index++;
        
            int fixPos = x[index - 1];
        
            while(index < x.Count && x[index] <= fixPos + k)
                index++;
                
            result++;
        }
        
        return result;
    }