Skip to content

1386. Cinema Seat Allocation

  • Time: $O(|\texttt{reservedSeats}|)$
  • Space: $O(|\texttt{reservedSeats}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
    int ans = 0;
    unordered_map<int, int> rowToSeats;

    for (const vector<int>& reservedSeat : reservedSeats) {
      const int row = reservedSeat[0];
      const int seat = reservedSeat[1];
      rowToSeats[row] |= 1 << (seat - 1);
    }

    for (const auto& [_, seats] : rowToSeats)
      if ((seats & 0b0111111110) == 0)
        // Can fit 2 four-person groups.
        ans += 2;
      else if ((seats & 0b0111100000) == 0 ||  // The left is not occupied.
               (seats & 0b0001111000) == 0 ||  // The middle is not occupied.
               (seats & 0b0000011110) == 0)    // The right is notoccupied.
        // Can fit 1 four-person group.
        ans += 1;

    // Any empty row can fit 2 four-person groups.
    return ans + (n - rowToSeats.size()) * 2;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
    int ans = 0;
    Map<Integer, Integer> rowToSeats = new HashMap<>();

    for (int[] reservedSeat : reservedSeats) {
      final int row = reservedSeat[0];
      final int seat = reservedSeat[1];
      rowToSeats.put(row, rowToSeats.getOrDefault(row, 0) | 1 << (seat - 1));
    }

    for (final int seats : rowToSeats.values())
      if ((seats & 0b0111111110) == 0)
        // Can fit 2 four-person groups.
        ans += 2;
      else if ((seats & 0b0111100000) == 0 || // The left is not occupied.
               (seats & 0b0001111000) == 0 || // The middle is not occupied.
               (seats & 0b0000011110) == 0)   // The right is notoccupied.
        // Can fit 1 four-person group.
        ans += 1;

    // Any empty row can fit 2 four-person groups.
    return ans + (n - rowToSeats.size()) * 2;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def maxNumberOfFamilies(self, n: int, reservedSeats: list[list[int]]) -> int:
    ans = 0
    rowToSeats = collections.Counter()

    for row, seat in reservedSeats:
      rowToSeats[row] |= 1 << (seat - 1)

    for seats in rowToSeats.values():
      if (seats & 0b0111111110) == 0:
        # Can fit 2 four-person groups.
        ans += 2
      elif ((seats & 0b0111100000) == 0 or
            (seats & 0b0001111000) == 0 or
            (seats & 0b0000011110) == 0):
        # Can fit 1 four-person group.
        ans += 1

    # Any empty row can fit 2 four-person groups.
    return ans + (n - len(rowToSeats)) * 2