Cerinta completa

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


antennae at houses and and provide complete coverage. There is no house at location to cover both and . Ranges of coverage, are , , and .

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 and , the number of houses in Hackerland and the range of each transmitter.
The second line contains space-separated integers describing the respective locations of each house .

Constraints

  • There may be more than one house at the same location.

Subtasks

  • for 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:

k-nearest(2).png

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

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:

k-nearest2(2).png

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

Limbajul de programare folosit: javascript

Cod:

//Problem: https://www.hackerrank.com/challenges/hackerland-radio-transmitters
//JavaScript
/*
Initial thoughts:
First, sort the array to so duplicate houses dont cause 
any errors when looking for where to place the transmitter.
Then, use greedy algorithm to always place the transmitter
at the house furthest to the right possible to cover
the range.
    
    
Time complexity: O(n log(n)) //Finding the furthest transmitter range
Space complexity: O(1)      //No additional space was used
*/

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function main() {
    var n_temp = readLine().split(' ');
    var n = parseInt(n_temp[0]);
    var k = parseInt(n_temp[1]);
    var houses = readLine().split(' ').map(Number).sort(function(a, b) { return a - b; });
    var house = houses[0], transmitter = houses[0], i = 0, towers = 0;

    while( i < n) {
        transmitter = houses[i];
        house = houses[i];
        towers++;
        while(i < n && (houses[i] - house) <= k){
            i++;
        }
        transmitter = houses[i-1];
        while(i < n && houses[i] <= transmitter + k){
            i++;
        }
    }
    console.log(towers);
}

Scor obtinut: 1.0

Submission ID: 464602735

Link challenge: https://www.hackerrank.com/challenges/hackerland-radio-transmitters/problem

Hackerland Radio Transmitters