← К задачам Массивы: 0/107 решено
Собеседование ← Предыдущая Следующая →

5808. Рассадка компаний в кинотеатре

Medium 0 решили
В кинотеатре n рядов, в каждом 10 мест с номерами от 1 до 10. Компания из четырёх человек садится целиком в одном ряду и только в один из трёх блоков: места 2–5, 4–7 или 6–9. Другие четвёрки мест не подходят: например, 3–6 компанию не сажают.

1  2  3  4  5  6  7  8  9  10
.  [----A-----]            .
         [----B-----]
               [----C-----]
Блоки A (2–5) и C (6–9) не пересекаются, поэтому в пустом ряду компаний две. Блок B (4–7) пересекается с обоими: его берут, только когда хотя бы один край уже закрыт. Места 1 и 10 — проходы. Они ни в один блок не входят и компании не мешают.

Дан список броней reserved. Каждая бронь — пара [ряд, место], ряды нумеруются с 1. Одно и то же место может встретиться несколько раз: оно всё равно занято один раз. Компания не садится на занятое место и не переходит в другой ряд.

Верните, сколько компаний можно рассадить.

Примеры:

Вход: n = 1, reserved = []
Выход: 2
Объяснение: Ряд пустой: компании садятся в 2–5 и в 6–9.
Вход: n = 3, reserved = [[1, 1], [1, 10], [2, 3]]
Выход: 5
Объяснение: Ряд 1: заняты только проходы 1 и 10, обе компании садятся. Ряд 2: место 3 закрывает блок 2–5, блок 6–9 свободен — одна компания. Ряд 3 пуст — ещё две. Итого 5.
Вход: n = 1, reserved = [[1, 2], [1, 9]]
Выход: 1
Объяснение: Края 2–5 и 6–9 закрыты, но центр 4–7 свободен. Туда садится одна компания.

Ограничения:

1 <= n <= 10^9 0 <= reserved.length <= 10^4 reserved[i].length == 2 1 <= reserved[i][0] <= n 1 <= reserved[i][1] <= 10

Теги:

Часто на собесе Жадные алгоритмы Хэш-таблица

Комментарии (0)

Зарегистрируйтесь или войдите, чтобы оставить комментарий

Пока нет комментариев. Будьте первым!