1386. 安排电影院座位

Powered by:NEFU AB-IN

Link

1386. 安排电影院座位

• 题意

  如上图所示，电影院的观影厅中有 n 行座位，行编号从 1 到 n ，且每一行内总共有 10 个座位，列编号从 1 到 10 。
  给你数组 reservedSeats ，包含所有已经被预约了的座位。比如说，researvedSeats[i]=[3,8] ，它表示第 3 行第 8 个座位被预约了。
  请你返回 最多能安排多少个 4 人家庭 。4 人家庭要占据 同一行内连续 的 4 个座位。隔着过道的座位（比方说 [3,3] 和 [3,4]）不是连续的座位，但是如果你可以将 4 人家庭拆成过道两边各坐 2 人，这样子是允许的。

• 思路

  由于排的数量很多，所以枚举每排的话是不现实的
  所以我们可以采用哈希表，来记录2~9有座位被占了的排（因为占1或10，和没占没什么区别，都是能做俩）
  其次，可以用二进制串来记录这排的位置情况，1代表占了（可以采用bitset，也可以采用int）
  最后取反一下，每行的状态，和left, mid, right进行&操作，如果&之后还是原值的话，那么说明可以放一个

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2022-09-09 14:13:18
  * @FilePath: \LeetCode\1386\1386.cpp
  * @LastEditTime: 2022-09-09 16:15:18
  */
  #include 
  using namespace std;
  
  // ---------------------
  #define N n + 100
  #define SZ(X) ((int)(X).size())
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  
  // #undef N
  // const int N = 1e5 + 10;
  
  static int IOS = []() {
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);
      return 0;
  }();
  
  class Solution
  {
    public:
      int maxNumberOfFamilies(int n, vector<vector<int>> &reservedSeats)
      {
          bitset<11> left{0b111100000}, mid{0b1111000}, right{0b11110};
  
          // 2~5 4~7 6~9
          unordered_map<int, bitset<11>> mp;
          for (auto v : reservedSeats)
          {
              int h = v[0], l = v[1];
              if (l >= 2 && l <= 9)
              {
                  mp[h].set(10 - l);
              }
          }
          int ans = (n - SZ(mp)) * 2;
          for (auto [h, b] : mp)
          {
              b = ~b;
              // DEBUG(right);
              if (((b & left) == left) || ((b & right) == right) || ((b & mid) == mid))
                  ans++;
          }
          return ans;
      }
  };
  
  // ---------------------
  
  // signed main()
  // {
  //     Solution solution;
  //     vector> a = {{1, 2}, {1, 3}, {1, 8}, {2, 6}, {3, 1}, {3, 10}};
  //     cout << solution.maxNumberOfFamilies(3, a);
  //     return 0;
  // }
  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
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63