Flatland Space Stations

Flatland is a country with a number of cities, some of which have space stations. Cities are numbered consecutively and each has a road of 1km length connecting it to the next city. It is not a circular route, so the first city doesn't connect with the last city. Determine the maximum distance from any city to its nearest space station.

Example

There are n = 3 cities and city 1 has a space station. They occur consecutively along a route. City  is  unit away and city 2 is 2-1 = 1 unit away. City 1 is 0 units from its nearest space station as one is located there. The maximum distance is 1.

Example:

Input:  n = 5, m = 2, c = {0, 4}
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int flatlandSpaceStations(int n, vector<int> c)
{

    sort(c.begin(), c.end());
    int maxDistance = c[0];
    for (int i = 1; i < c.size(); i++)
    {
        int distance = (c[i] - c[i - 1]) / 2;
        if (maxDistance < distance)
            maxDistance = distance;
    }
    int last = (n - 1) - c[c.size() - 1];
    if (last < maxDistance)
        return maxDistance;
    return last;
}

int main()
{

    int n = 5;
    int m = 2;

    vector<int> c = {0, 4};

    cout << flatlandSpaceStations(n, c) << "\n";

    return 0;
}