Show problems as
Classic problem #1386MediumArrayHash TableGreedyBit Manipulation

Cinema Seat Allocation

Real-world version: Study Pods in the Lecture Hall
Tracked in this browser only
Read Cinema Seat Allocation on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A lecture hall has benches long benches, numbered 1 to benches. Every bench has ten slots, numbered 1 to 10 along it. A central walkway cuts the bench between slot 5 and slot 6, and slots 1 and 10 sit hard against the side walls and are kept clear for access, so no group may use them.

A study pod seats four people in four consecutive slots of one bench, and the hall only allows three arrangements for it: slots 2 to 5, wholly on the left of the walkway; slots 4 to 7, centred on the walkway; or slots 6 to 9, wholly on the right of it.

taken[i] = [bench_i, slot_i] lists the slots already booked by individual students; all entries are distinct. A pod cannot use a booked slot, and two pods on the same bench cannot share a slot.

Return the greatest number of study pods the hall can seat.

Examples

Example 1

Input
benches = 4, taken = [[1, 2], [1, 3], [1, 8], [2, 6], [3, 1], [3, 10]]
Output
6

Bench 3 has only its two wall slots booked and bench 4 has nothing booked, so those two benches take two pods each. Benches 1 and 2 each have room for one pod.

Example 2

Input
benches = 1, taken = [[1, 2], [1, 9]]
Output
1

Slot 2 spoils the left arrangement and slot 9 spoils the right one, while slots 4 to 7 are all free, so one pod is seated.

Example 3

Input
benches = 1, taken = [[1, 1]]
Output
2

The only booking is against a side wall, which no pod may use anyway, so the bench takes a pod on either side of the walkway.

Constraints

  • 1 <= benches <= 10^9
  • 1 <= taken.length <= min(10 * benches, 10^4)
  • taken[i] == [bench_i, slot_i]
  • 1 <= bench_i <= benches
  • 1 <= slot_i <= 10
  • All taken[i] are distinct.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def most_pods(benches: int, taken: list[list[int]]) -> int:
Java
public int mostPods(int benches, int[][] taken)

More on the same topics