Cinema seat allocation

Array Hash Table Greedy Bit Manipulation

43.6% acceptance

Feb 25, 2026

974

417

A cinema has n rows of seats, numbered from 1 to n and there are ten seats in each row, labelled from 1 to 10 as shown in the figure above. Given the array reservedSeats containing the numbers of seats already reserved, for example, reservedSeats[i] = [3,8] means the seat located in row 3 and labelled with 8 is already reserved. Return the maximum number of four-person groups you can assign on the cinema seats. A four-person group occupies four adjacent seats in one single row. Seats across an aisle (such as [3,3] and [3,4]) are not considered to be adjacent, but there is an exceptional case on which an aisle split a four-person group, in that case, the aisle split a four-person group in the middle, which means to have two people on each side.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_number_of_families(n: i32, reserved_seats: Vec<Vec<i32>>) -> i32 {
    use std::collections::HashMap;
    let mut rows: HashMap<i32, u32> = HashMap::new();
    for seat in &reserved_seats {
      let (r, c) = (seat[0], seat[1] as u32);
      *rows.entry(r).or_insert(0) |= 1 << c;
    }
    // Seats numbered 1-10. 
    // Left group: seats 2,3,4,5 -> bits 2,3,4,5
    // Middle group: seats 4,5,6,7 -> bits 4,5,6,7
    // Right group: seats 6,7,8,9 -> bits 6,7,8,9
    let left: u32   = (1<<2)|(1<<3)|(1<<4)|(1<<5);
    let middle: u32 = (1<<4)|(1<<5)|(1<<6)|(1<<7);
    let right: u32  = (1<<6)|(1<<7)|(1<<8)|(1<<9);
    let mut ans = 2 * (n - rows.len() as i32); // rows with no reserved seats get 2
    for &mask in rows.values() {
      let has_left = mask & left == 0;
      let has_right = mask & right == 0;
      if has_left && has_right {
        ans += 2;
      } else if has_left || (mask & middle == 0) || has_right {
        ans += 1;
      }
    }
    ans
  }
}