0481MediumArrayHash TableGreedyBit Manipulation

Study Pods in the Lecture Hall

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def most_pods(benches: int, taken: list[list[int]]) -> int:

Java

public int mostPods(int benches, int[][] taken)

The intended approach

Time O(len(taken))Space O(number of distinct benches in taken)

There can be a billion benches but at most ten thousand bookings, so only the benches that appear in `taken` are worth looking at; every other bench looks exactly like an empty bench and takes two pods. Collapse each mentioned bench into a ten-bit word with a bit per booked slot, then test the three arrangements against that word with three masks. If the two side arrangements are both clear they can be seated together, since they share no slot; otherwise any single clear arrangement is worth one pod, and nothing clear is worth none.

Pythonentry point: most_pods

def most_pods(benches, taken):
    # One 10-bit word per bench that has a booking; untouched benches are all alike.
    # time O(len(taken)), space O(number of benches that appear in taken)
    LEFT = (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5)
    CENTRE = (1 << 4) | (1 << 5) | (1 << 6) | (1 << 7)
    RIGHT = (1 << 6) | (1 << 7) | (1 << 8) | (1 << 9)
    booked = {}
    for entry in taken:
        bench, slot = entry[0], entry[1]
        booked[bench] = booked.get(bench, 0) | (1 << slot)
    total = 2 * (benches - len(booked))
    for word in booked.values():
        left_clear = (word & LEFT) == 0
        right_clear = (word & RIGHT) == 0
        if left_clear and right_clear:
            total += 2
        elif left_clear or right_clear or (word & CENTRE) == 0:
            total += 1
    return total

The obvious version

For a given set of booked slots, try all eight subsets of the three arrangements and keep the largest subset whose spans avoid the bookings and avoid each other. Run that once on an empty bench to price the benches nobody booked, and once per booked bench.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_most_pods(benches, taken):
    spans = [set(range(2, 6)), set(range(4, 8)), set(range(6, 10))]

    def bf_fit(used):
        best = 0
        for pick in range(8):
            chosen = [spans[b] for b in range(3) if (pick >> b) & 1]
            filled = set()
            ok = True
            for span in chosen:
                if span & used or span & filled:
                    ok = False
                    break
                filled |= span
            if ok and len(chosen) > best:
                best = len(chosen)
        return best

    per_bench = {}
    for entry in taken:
        per_bench.setdefault(entry[0], set()).add(entry[1])
    total = bf_fit(set()) * (benches - len(per_bench))
    for used in per_bench.values():
        total += bf_fit(used)
    return total

How this problem was checked

Reference solution executed against 8 test cases — 8 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in