LeetCode 1386. Cinema Seat Allocation

, , , ,

Question

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 families you can allocate on the cinema seats. A four-person family occupies fours seats in one row, that are next to each other. Seats across an aisle (such as [3,3] and [3,4]) are not considered to be next to each other, however, It is permissible for the four-person family to be separated by an aisle, but in that case, exactly two people have to sit on each side of the aisle.

Example

1
2
3
4
5
6
7
8
9
Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
Output: 4
Explanation: The figure above shows the optimal allocation for four families, where seats mark with blue are already reserved and contiguous seats mark with orange are for one family. 

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

Input: n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
Output: 4

Solution

根据本题的限制条件，我们可以观察出，其中只存在三种放置方式，分别如下所示。

1
2
3
1. [2,3, ,4,5]
2. [6,7, ,8,9]
3. [4,5,6,7]

这里连续的四个放置在最后的原因是这样可以最大限度的放置最多的人，如果将这个写在前面则会导致本身前后可以使用的区域无法使用。这里值得注意的是二维数组可能在某一行没有安置，所以我们可以有最多两种方式安置。

Code

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
public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
        if (reservedSeats == null || reservedSeats.length == 0 ||
           reservedSeats[0] == null || reservedSeats[0].length == 0) return 0;
        HashMap<Integer, HashSet<Integer>> filled = new HashMap<>();
        for (int[] seats : reservedSeats) {
            filled.putIfAbsent(seats[0], new HashSet<>());
            filled.get(seats[0]).add(seats[1]);
        }
        int res = (n - filled.size()) * 2;
        // [2, 3, , 4, 5], [6, 7, , 8, 9], [4, 5, 6, 7]
        for (int row : filled.keySet()) {
            boolean placed = false;// 用来检查中间任意一个元素是否被占用
            if (!filled.get(row).contains(2) && !filled.get(row).contains(3) 
                && !filled.get(row).contains(4) && !filled.get(row).contains(5)){
                res++;
                placed = true;
            }
            
            if (!filled.get(row).contains(6) && !filled.get(row).contains(7) 
                && !filled.get(row).contains(8) && !filled.get(row).contains(9)){
                res++;
                placed = true;
            }
            
            // 检查中间的可能性
            if (!placed) {
                  if (!filled.get(row).contains(4) && !filled.get(row).contains(5) 
                      && !filled.get(row).contains(6) && !filled.get(row).contains(7)){
                      res++;
                }
            }
        }
        return res;
    }

Reference