Task Livecoding Java Best Seat Distance | IT Ментор

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

Условие задачи:
🔥 Места в кинотеатре расположены в один ряд (массив seats из 0 и 1).

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

Только что пришедший зритель выбирает такое свободное место, чтобы максимизировать расстояние до ближайшего сидящего.
Гарантируется, что есть хотя бы один занятый и хотя бы одно свободное место.
Напишите метод findBestSeatDist, который возвращает это максимальное расстояние.


Пример:
[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) {

}

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

Подсказки

💡 Найдите индексы занятых мест и разбейте ряд на три типа сегментов:

до первого занятого
между двумя занятыми
после последнего занятого
💡 Для каждого сегмента вычислите максимальное возможное расстояние до ближайшего соседа:
в краевых сегментах расстояние равно длине сегмента
в внутренних — (gap + 1) / 2
💡 Итог — максимальное среди этих значений.

Решение

public class Cinema {
    public int findBestSeatDist(int[] seats) {
        int n = seats.length;
        int last = -1;
        int maxDist = 0;
        
        // 1) Пройтись слева направо
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                if (last < 0) {
                    // сегмент свободных мест слева от первого занятого
                    maxDist = i;
                } else {
                    // сегмент между двумя занятыми
                    int gap = i - last - 1;
                    maxDist = Math.max(maxDist, (gap + 1) / 2);
                }
                last = i;
            }
        }
        // 2) Учесть сегмент свободных мест справа от последнего занятого
        maxDist = Math.max(maxDist, n - 1 - last);
        
        return maxDist;
    }
}