DDSA Solutions

1386. Cinema Seat Allocation

MediumView on LeetCode
ArrayHash TableGreedyBit Manipulation

Problem Overview

A four-person group only uses seats 2-5, 4-7, or 6-9.

Intuition

A four-person group only uses seats 2-5, 4-7, or 6-9. Seats 1 and 10 never matter. An empty row always takes two groups (left and right). n can be 1e9, so only walk rows that have a reserved seat in 2-9, start from 2*n, and subtract what those rows lose.

Algorithm

  1. 1For each reserved seat, skip 1 and 10. Pack seats 2-9 into a bitmask per row (bit 0 = seat 2).
  2. 2ans = 2 * n.
  3. 3For each touched row: left = seats 2-5, mid = 4-7, right = 6-9.
  4. 4If left, mid, and right are all blocked, subtract 2. Otherwise subtract 1 (the row still fits one group, or would have fit two if empty).
  5. 5Return ans.

Example Walkthrough

Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]

  1. 1.Empty-row baseline: 3 rows * 2 = 6.
  2. 2.Row 1: 2,3,8 reserved - left and right blocked, middle 4-7 still open, so 1 group (subtract 1).
  3. 3.Row 2: seat 6 blocks mid and right; left 2-5 is still open, so 1 group (subtract 1).
  4. 4.Row 3: only 1 and 10 reserved, ignored, still 2 groups. Answer 4.

Output: 4

Common Pitfalls

  • •Do not iterate 1..n - n can be 1e9.
  • •Aisle seats 1 and 10 do not block any family; a row with only those reserved still fits 2 groups.
  • •Left and right together are 2 groups; you cannot also count the middle on the same row.
  • •A row that appears in the map has some seat in 2-9 reserved, so it cannot fit two groups - subtract 1 if any of left/mid/right is free, else subtract 2.
1386.cs
C#
// Approach: Each row can seat at most 2 four-person groups (seats 2-5 and 6-9).
// Seats 1 and 10 never block a group. Pack reserved seats 2-9 into a bitmask per
// touched row. Start from 2*n and subtract 1 if any block is blocked, or 2 if
// left, mid, and right are all blocked.
// Complexity: O(m) time and O(m) space (m = reservedSeats.length).
public class Solution
{
    public int MaxNumberOfFamilies(int n, int[][] reservedSeats)
    {
        var rowToSeats = new Dictionary<int, int>();

        foreach (var rs in reservedSeats)
        {
            int seat = rs[1];
            if (seat == 1 || seat == 10)
                continue;

            int row = rs[0];
            rowToSeats.TryGetValue(row, out int mask);
            rowToSeats[row] = mask | (1 << (seat - 2));
        }

        int ans = n * 2;
        foreach (int seats in rowToSeats.Values)
        {
            bool left = (seats & 0b11110000) != 0;
            bool mid = (seats & 0b00111100) != 0;
            bool right = (seats & 0b00001111) != 0;
            ans -= left && mid && right ? 2 : 1;
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems