LeetCode 解題筆記：1386. Cinema Seat Allocation

作者：王一哲
日期：2026年8月19日


LeetCode 題目連結：1386. Cinema Seat Allocation

解題想法

中等難度的題目。題目給一個二維陣列 $reservedSeats$，其中每一個元素有兩項，分別代表第幾列、第幾個座位已經被預約。所有的座位共有 $n$ 列，每列有編號 1 到 10 的座位。如果有 4 個人一組的客人，只能被安排在 $(2, 3, 4, 5)$、$(4, 5, 6, 7)$ 或 $(6, 7, 8, 9)$ 而且沒有被預約的座位。題目要計算最多可以安排幾組 4 個人的客人。由於這題的 $n$ 最大可以到 $10^9$，如果建一個 $n \times n$ 的陣列並標記每個座位是否被預約，這樣會超出記憶體上限。但是這題的 $reserveSeats$ 的長度最大值是 $10 \times n$ 及 $10^4$ 之中較小者，實際上需要標記的被預約座位並不多，可以用字典 $reserved$ 儲存已預約座位的列狀態就好。甚至可以進一步用二進位 bitmask 記錄座位狀態，用 0 代表空位，用 1 代表被預約的座位，例如 $0b00000111100$ 代表第 2、3、4、5 號座位被預約，這樣可以節省記憶體，而且用 bitwise 操作速度很快。

計算答案時，先處理整列都是空位的部分，每一列可以放入 2 組人，因此答案 $ans = (n - len(reservec)) \times 2$。再從 $reserved$ 讀取有被預約的座位狀態 $mask$，如果 $0b00000111100 & mask == 0$ 代表可以將這組人放入 $(2, 3, 4, 5)$ 號座位；如果 $0b01111000000 & mask == 0$ 代表可以將這組人放入 $(6, 7, 8, 9)$ 號座位；如果 $0b00011110000 & mask == 0$ 代表可以將這組人放入 $(4, 5, 6, 7)$ 號座位。如果同時可以放入 $(2, 3, 4, 5)$ 及 $(6, 7, 8, 9)$ 號座位，答案加 2；如果以上 3 種狀態任何 1 種成立，答案加 1。

Python 程式碼

用 defaultdict 寫起來比較方便，但是速度比較慢。Runtime: 30 ms, beats 78.66%. Memory: 22.95 MB, beats 53.73%.

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        # 改用字典儲存每列已經預約的座位
        reserved = defaultdict(int)
        for r, c in reservedSeats:
            reserved[r] |= (1 << c)
        
        # 用貪心法計算組數
        ans = (n - len(reserved)) * 2  # 組數，如果整列都沒有預約的座位，可以放入 2 組人
        for r, mask in reserved.items():  # 處理有預約座位的列
            left = (0b00000111100 & mask) == 0  # (2, 3, 4, 5) 是否為空位
            right = (0b01111000000 & mask) == 0  # (6, 7, 8, 9) 是否為空位
            mid = (0b00011110000 & mask) == 0  # (4, 5, 6, 7) 是否為空位
            if left and right:  # 左、右都有空位，可以放入 2 組
                ans += 2
            elif left or mid or right:  # 左、中、右只有 1 組空位
                ans += 1
        return ans

用預設的 dict 寫起來比較麻煩，但是速度比較快。Runtime: 19 ms, beats 97.43%. Memory: 22.50 MB, beats 94.60%.

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        # 改用預設的字典儲存每列已經預約的座位
        reserved = dict()
        for r, c in reservedSeats:
            if r not in reserved:
                reserved[r] = (1 << c)
            else:
                reserved[r] |= (1 << c)
        
        # 用貪心法計算組數
        ans = (n - len(reserved)) * 2  # 組數，如果整列都沒有預約的座位，可以放入 2 組人
        for r, mask in reserved.items():  # 處理有預約座位的列
            left = (0b00000111100 & mask) == 0  # (2, 3, 4, 5) 是否為空位
            right = (0b01111000000 & mask) == 0  # (6, 7, 8, 9) 是否為空位
            mid = (0b00011110000 & mask) == 0  # (4, 5, 6, 7) 是否為空位
            if left and right:  # 左、右都有空位，可以放入 2 組
                ans += 2
            elif left or mid or right:  # 左、中、右只有 1 組空位
                ans += 1
        return ans

C++ 程式碼

Runtime: 34 ms, beats 59.63%. Memory: 66.60 MB, beats 48.48%.

class Solution {
public:
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        // 用字典儲存每列的座位狀態，1 代表已預約，0 代表空位
        unordered_map<int, int> reserved;  // {row: mask}
        for(auto it : reservedSeats) {
            reserved[it[0]] |= (1 << it[1]);
        }
        
        // 用 bitmask 處理空位，檢查可以放入的組數
        int ans = (n - (int)reserved.size()) * 2;  // 整列都是空位，一列可以放 2 組
        for(auto it : reserved) {
            int mask = it.second;
            bool left = (0b00000111100 & mask) == 0;
            bool right = (0b01111000000 & mask) == 0;
            bool mid = (0b00011110000 & mask) == 0;
            if (left && right) {  // 左、右都有空位，可以放 2 組
                ans += 2;
            } else if (left || mid || right) {  // 左、中、右只有 1 組有空位
                ans++;
            }
        }
        return ans;
    }
};