Место в кинотеатре максимально далеко от других зрителей (Maximize Distance to Closest Person)

Условие

Место в кинотеатре максимально далеко от других зрителей (Maximize Distance to Closest Person)

Условие: Места в кинотеатре расположены в один ряд и представлены массивом из нулей и единиц, где 1 — занятое место, 0 — свободное. Только что пришедший зритель выбирает свободное место так, чтобы расстояние до ближайшего уже сидящего зрителя было максимальным. Напишите функцию, которая возвращает это максимальное расстояние (в местах) от выбранного места до ближайшего занятого. Гарантируется, что в ряду есть хотя бы одно занятое место и хотя бы одно свободное.

Входные данные: seats — массив из 0 и 1, длина от 2 до 10^5, содержит хотя бы одну 1 и хотя бы один 0.

Выходные данные: Целое число — максимальное расстояние от выбранного места до ближайшего занятого.

Ответ

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

def max_distance(seats):
    previous = -1
    best = 0
    for index, occupied in enumerate(seats):
        if occupied:
            if previous == -1:
                best = index
            else:
                best = max(best, (index - previous) // 2)
            previous = index
    return max(best, len(seats) - 1 - previous)

Краевые промежутки ограничены зрителем только с одной стороны, поэтому их длина целиком является доступным расстоянием. Между занятыми местами на расстоянии d максимальная дистанция до ближайшего равна d // 2. Гарантии условия исключают пустой ряд без зрителей. Время O(n), дополнительная память O(1).