Cafeteria Seating

See all coding puzzles and patterns here.

Difficulty: Medium

Problem Definition

A cafeteria table consists of $n$ seats, numbered 1 to $n$. There must be $k$ empty seats to the left and right of everyone sitting on the table, unless they are sitting on the left or the right end of the table, in which case they don't need $k$ empty seats on the left or right respectively. If you are given an array $s$ of seating positions for the people currently sitting on the bench, find the number of additional people who can still sit at the table.

Examples

Some examples to verify our solution.

# x = occupied seat, _ = required empty seat, o = newly occupied seat
# 1                 10
# _ x _ o _ x _ o _ o
assert cafe_seating(n=10, k=1, s=[2, 6]) == 3
# 1                           15
# o _ _ _ _ x _ _ _ _ x _ _ x _
assert cafe_seating(n=15, k=2, s=[11, 6, 14]) == 1
# 1                 10
# o _ x _ x _ x _ o _
assert cafe_seating(n=10, k=1, s=[3, 5, 7]) == 2

Destructive Solution

We want to find the gaps of size $k + 1$ for the occupant between the blocked-off prior seats on the bench and the next occupant. For each such gap, we will compute the minimum number of occupants who can occupy the gap and add that number to the answer. For the final gap, we want to add one to `seat_count` and take the ceiling instead of the floor of the division to allow occupation of the last seat.

This solution is destructive of `s`, since we sort it. A non-destructive solution is below.

def cafe_seating(n, k, s):
    ans = 0
    s.sort()
    curr = 1
    min_req = k + 1
    for nxt in s:
        ans += math.floor((nxt - curr) / min_req)
        curr = nxt + min_req
    ans += math.ceil((n - curr + 1) / min_req)
    return ans

Destructive Solution Complexity

Let $m = $ len(s)

Space complexity should be $O(1)$ since we are only maintaining some scalar auxiliary variables. This is assuming our sort is done in-place.

Runtime complexity should be $O(m \cdot log(m))$ due to our sort of s.

Non-Destructive Solution