Hackerland Radio Transmitters

Solutions

This is a classical greedy interval coverage problem that can be solved in a few ways. The first solution consists in sorting the positions, then walking left-to-right and for each uncovered position, placing the transmitter as far right as possible while still covering it, then skipping everything the transmitter reaches. This solution is \(O(N \cdot logN)\) due to sorting. To search the rightmost position can be done either linearly or using a binary search, since the array is sorted. This is a C++ implementation of the latter approach:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


int hackerlandRadioTransmitters(vector<int> x, int k)
{
    sort(begin(x), end(x));
    auto transmitters = 0;
    size_t i = 0;
    while (i < x.size()) 
    {
        const auto it = upper_bound(begin(x) + i, end(x), x[i] + k);
        const auto transmitterPos = *prev(it);
        const auto covered = upper_bound(it, end(x), transmitterPos + k);
        i = static_cast<int>(distance(begin(x), covered));
        ++transmitters;
    }
    return transmitters;
}

In essence, each iteration searches for the rightmost house that can still cover the current one. If the next house is too far from the current house (e.g. x[i+1] - x[i] > k), then the current house must be covered by a radio placed on itself. Otherwise, the current house is covered by the rightmost house whose range still includes it. upper_bound binary searches for the first house whose value is greater than the given one.

Using iterators directly:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


int hackerlandRadioTransmitters(vector<int> x, int k)
{
    sort(begin(x), end(x));
    int transmitters = 0;
    auto curr = begin(x);
    while (curr != end(x)) 
    {
        curr = upper_bound(curr, x.end(), *prev(upper_bound(curr, end(x), *curr + k)) + k);
        ++transmitters;
    }
    return transmitters;
}

To avoid sorting and binary searching, we can allocate a fixed‑size array (since the domain is limited to \(10^5\)) to track all house positions and then scan this array left to right to determine the transmitter for each house. However, because this position array is “dense”, it also includes indices where no houses exist. As a result, we can’t jump directly to the next house and must find it linearly.

Here is a possible implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


int hackerlandRadioTransmitters(vector<int> x, int k)
{
    constexpr auto maxPos = 100000;

    array<bool, maxPos + 1> hasHouse{};
    for (int pos : x)
    {
        hasHouse[pos] = true;
    }

    int transmitters = 0;
    int i = 0;

    while (i <= maxPos)
    {
        if (!hasHouse[i])
        {
            ++i;
            continue;
        }

        int limit = std::min(i + k, maxPos);
        int transmitterPos = i;
        for (int j = i; j <= limit; ++j)
        {
            if (hasHouse[j]) transmitterPos = j;
        }

        i = transmitterPos + k + 1;
        ++transmitters;
    }

    return transmitters;
}

A slight optimization consists in iterating backwards from limit to i in the inner loop. Changing this:

1
2
3
4


for (int j = i; j <= limit; ++j)
{
    if (hasHouse[j]) transmitterPos = j;
}

to this:

1
2
3
4
5
6
7
8
9


for (int j = limit; j >= i; --j)
{
    if (hasHouse[j])
    {
        transmitterPos = j;
        break;
    }
        
}

This avoids scanning the entire range in the best case.

Note also that we can replace the array of bools with a bitset:

1

bitset<maxPos + 1> hasHouse;

This solution is linear in time and constant in space (since the domain size is fixed). However, the main loop visits empty positions one-by-one between coverage zones. If houses are very sparse (e.g. houses at 0 and 100000 with k = 1), we’d step through ~100'000 empty cells.