Поиск оптимального места в кинотеатре

29. Найти максимальное расстояние до ближайшего занятого места

Условие задачи:
Дан массив seats, описывающий один ряд мест в кинотеатре:

1 — место занято;
0 — место свободно.

Новый зритель выбирает свободное место так, чтобы расстояние до ближайшего занятого места было максимально возможным.

Гарантируется, что в массиве есть хотя бы одно занятое и хотя бы одно свободное место.

Необходимо реализовать метод findBestSeatDist(), который возвращает максимальное расстояние до ближайшего занятого места.

Код:

public int findBestSeatDist(int[] seats) {
    // TODO
}

Примеры:

[1, 0, 0, 0, 1]                → 2
[1, 0, 1, 0, 0, 1, 0, 0, 0, 1] → 2
[1, 0, 1, 0]                   → 1

Спойлеры к решению

Подсказки

💡 Свободные места можно разделить на три типа участков: до первого занятого, между двумя занятыми и после последнего занятого.
💡 На краях лучшее место находится максимально далеко от единственного ближайшего занятого места.
💡 Между двумя занятыми местами оптимально выбрать место примерно посередине.
💡 Достаточно одного прохода по массиву, запоминая индекс предыдущего занятого места.

Решение

public int findBestSeatDist(int[] seats) {
    int lastOccupied = -1;
    int maxDistance = 0;

    for (int i = 0; i < seats.length; i++) {
        if (seats[i] != 1) {
            continue;
        }

        if (lastOccupied == -1) {
            // Свободные места до первого занятого.
            maxDistance = i;
        } else {
            // Расстояние между двумя занятыми местами.
            int distance = (i - lastOccupied) / 2;
            maxDistance = Math.max(maxDistance, distance);
        }

        lastOccupied = i;
    }

    // Свободные места после последнего занятого.
    maxDistance = Math.max(
            maxDistance,
            seats.length - 1 - lastOccupied
    );

    return maxDistance;
}

Рассмотрим три возможных случая.

Если свободные места находятся до первого занятого, например:

[0, 0, 0, 1]

лучше выбрать самое левое место. Расстояние будет:

Поэтому при обнаружении первого занятого места:

maxDistance = i;

Если свободные места находятся между двумя занятыми:

[1, 0, 0, 0, 1]

расстояние между индексами занятых мест равно 4, поэтому максимальное расстояние до ближайшего из них:

(4 - 0) / 2 = 2

В коде:

int distance = (i - lastOccupied) / 2;

Например:

[1, 0, 0, 0, 1]
       ^

лучшее место находится посередине и имеет расстояние 2.

Наконец, если свободные места находятся после последнего занятого:

[1, 0, 0, 0]

лучше выбрать последнее место:

seats.length - 1 - lastOccupied

Временная сложность — O(n), поскольку массив просматривается один раз.

Дополнительная память — O(1).