1386. Cinema Seat Allocation Medium

1/**
2 * [1386] Cinema Seat Allocation
3 *
4 * <img alt="" src="https://assets.leetcode.com/uploads/2020/02/14/cinema_seats_1.png" style="width: 400px; height: 149px;" />
5 * 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.
6 * 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.
7 * 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.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2020/02/14/cinema_seats_3.png" style="width: 400px; height: 96px;" />
11 * 
12 * Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
13 * Output: 4
14 * Explanation: The figure above shows the optimal allocation for four groups, where seats mark with blue are already reserved and contiguous seats mark with orange are for one group.
15 * 
16 * Example 2:
17 * 
18 * Input: n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
19 * Output: 2
20 * 
21 * Example 3:
22 * 
23 * Input: n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
24 * Output: 4
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	1 <= n <= 10^9
30 * 	1 <= reservedSeats.length <= min(10*n, 10^4)
31 * 	reservedSeats[i].length == 2
32 * 	1 <= reservedSeats[i][0] <= n
33 * 	1 <= reservedSeats[i][1] <= 10
34 * 	All reservedSeats[i] are distinct.
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/cinema-seat-allocation/
40// discuss: https://leetcode.com/problems/cinema-seat-allocation/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn max_number_of_families(n: i32, reserved_seats: Vec<Vec<i32>>) -> i32 {
46        0
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_1386() {
58    }
59}
60