Hotel Coverage

See the original problem on HackerRank.

Solutions

This problem falls into the greedy category.

A hotel can accomodate all customers in a distance of \(-k\) and \(+k\). We should find the smallest amount of intervals of length \(2k\) that cover all the positions of the customers.

First of all, we sort the positions of the customers.

We iterate over all the sorted positions and, at each step, we calculate the difference between adjacent positions. We keep track of the interval by incrementing a running sum of the such differences.

All the customers that are less than distance \(2k\) from the first position do not need a new hotel. On the other hand, if there is a position that is further away, we reset the running sum and add a new hotel.

Here is a C++ implementation:

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

sort(begin(customers), end(customers));
auto hotels = 1, longestDistance=0;
    
for (auto i=1; i<customers.size(); ++i)
{
    auto diff = customers[i] - customers[i-1];
    if (ceil(((float)longestDistance + diff)/2) <= k)
    {
        longestDistance += diff;
    }
    else
    {
        hotels++;
        longestDistance = 0;
    }
}

return hotels;

Just to experiment a bit more with the problem, we can turn the domain from the space of positions to the space of distances by calculating adjacent differences first.

In C++, we can use adjacent_difference:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

sort(begin(customers), end(customers));
adjacent_difference(begin(customers), end(customers), begin(customers));
customers.erase(begin(customers));
       
auto hotels = 1, longestDistance=0;
    
for (auto i : customers)
{
    if (ceil(((float)longestDistance + i)/2) <= k)
    {
        longestDistance += i;
    }
    else
    {
        hotels++;
        longestDistance = 0;
    }
}

cout << hotels;

Another similar but easier approach, consists in iterating through the customers and adding an hotel when the distance between the current customer and the last added hotel is greater than k.

Here is an example by Elia Giacobazzi:

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

n, k = map(int, input().strip().split())
positions = sorted(list(set(map(int, input().strip().split()))))

hotel = positions[0] + k

cnt = 1
for p in positions:
    if abs(hotel - p) > k:
        hotel = p + k
        cnt += 1
    
print(cnt)

An alternative solution which does not involve sorting uses extra space. The idea is to pre-allocate an array of \( 1'000'000'000 \) bools to flag if any customer is at the corresponding position. Clearly, this approach is less efficient because the problem domain is 1000-times bigger than the input length. However, it’s worth knowing it when the problem constraints are different.

Having such an array, we can just greedily jump by \(2*k + 1\) steps (\(2k\) is the maximum coverage span) to find the next \(true\) in the array. Here is an example in C++:

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

int N, K; cin >> N >> K;
// better alternatives exist
vector<bool> v(1'000'000'000+1);
while (cin>>N)
    v[N] = true;

auto hotels = 0;
auto it = begin(v);
while (it = find(it, end(v), true), it != end(v))
{       
    hotels++;
    if (distance(it, end(v)) < 2*K +1)
        break;
    advance(it, 2*K + 1);
}

cout << hotels;

Interesting variations:

• group people which will go to the same hotel (e.g. printing them);
• limit the number and position of hotels (e.g. additional array with hotel positions);
• limit the number of available rooms per hotel.