Maximum Cinema Seat Allocation
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.
Examples:
Input: n = 3, reservedSeats = {{1, 1}, {1, 10}, {2, 6}, {3, 2}, {3, 3}, {3, 8}}
Output: 4
Explanation: The first row will have two families, second row will have one family and the third row will also have one family.Input: n = 2, reservedSeats = {{1, 1}, {2, 8}, {1, 6}}
Output: 2
Explanation: The first row will have one family and the second row will also have one family.
Approach: To solve the problem, follow the below approach:
We can only place groups of 4 from 2, 4 and 6. For a particular row, we should start placing greedily from 2, in order to get max. seats We can apply binary search and find lower bound of occupied seat in O(log N).
- If current seat can be taken, we will take it(and move 4 steps ahead)
- Else we try to place at 2 steps ahead.
Step-by-step approach:
- Iterate through the reservedSeats vector.
- For each reserved seat, add the seat number to the vector associated with the corresponding row in the hash map.
- Count the number of families that can be seated.
- Initialize a variable ans to keep track of the number of families that can be seated.
- Initialize a variable availableRows to keep track of the number of rows without any reserved seats.
- Create a hash map to store reserved seats for each row:
- Iterate through each row in the hash map:
- Sort the reserved seats in the current row in ascending order.
- Start checking the seats from seat 2 and move forward in steps of 4.
- For each position, find the first reserved seat that is at least 4 positions away from the current seat using the lower_bound function.
- If such a seat is found, it means a family can be seated, so increment the count variable and move to the next possible family seat (position E).
- If no such seat is found, move to the next seat (position B or C).
- Add the number of families that can be seated in the available rows (each row can seat 2 families) to the count variable.
- Iterate through each row in the hash map:
- Return the final value of the count variable.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
using namespace std;
int maxNumberOfFamilies(int n,
vector<vector<int> >& reservedSeats)
{
// Create a hash map to store reserved seats for each
// row.
unordered_map<int, vector<int> > mp;
for (int i = 0; i < reservedSeats.size(); i++) {
mp[reservedSeats[i][0]].push_back(
reservedSeats[i][1]);
}
// Variable to store the total number of families
int ans = 0;
// Rows with all seats vacant
int availableRows = n - mp.size();
// Iterate through each row with reserved seats.
for (auto it : mp) {
vector<int> seats = it.second;
// Sort reserved seats in ascending order.
sort(seats.begin(), seats.end());
// Start checking from seat 2
int seat = 2;
while (seat <= 6) {
// Find the first reserved seat that is at least
// 4 positions away from the current seat.
auto lowerBound = lower_bound(
seats.begin(), seats.end(), seat);
if (lowerBound == seats.end()
|| *(lowerBound)-seat >= 4) {
ans++;
// Move to the next possible family seat
seat += 4;
}
else {
// Move to the next seat
seat += 2;
}
}
}
// Add families that can be seated in available rows
// (each row can seat 2 families).
ans += availableRows * 2;
return ans;
}
int main()
{
// Input: n = 3, reservedSeats =
// [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
int n = 3;
vector<vector<int> > reservedSeats
= { { 1, 2 }, { 1, 3 }, { 1, 8 },
{ 2, 6 }, { 3, 1 }, { 3, 10 } };
int maxFamilies = maxNumberOfFamilies(n, reservedSeats);
cout
<< "Maximum number of families that can be seated: "
<< maxFamilies << endl;
return 0;
}
import java.util.*;
public class MaxNumberOfFamilies {
public static int maxNumberOfFamilies(int n, List<List<Integer>> reservedSeats) {
// Create a hash map to store reserved seats for each row.
Map<Integer, List<Integer>> mp = new HashMap<>();
for (List<Integer> seat : reservedSeats) {
mp.computeIfAbsent(seat.get(0), k -> new ArrayList<>()).add(seat.get(1));
}
// Variable to store the total number of families
int ans = 0;
// Rows with all seats vacant
int availableRows = n - mp.size();
// Iterate through each row with reserved seats.
for (Map.Entry<Integer, List<Integer>> entry : mp.entrySet()) {
List<Integer> seats = entry.getValue();
// Sort reserved seats in ascending order.
Collections.sort(seats);
// Track if seats are available for family in specific groups
boolean leftGroup = true, middleGroup = true, rightGroup = true;
for (int seat : seats) {
if (seat >= 2 && seat <= 5) {
leftGroup = false;
}
if (seat >= 4 && seat <= 7) {
middleGroup = false;
}
if (seat >= 6 && seat <= 9) {
rightGroup = false;
}
}
// Count families that can be seated in this row
if (leftGroup || rightGroup) {
ans++;
}
if (middleGroup) {
ans++;
}
}
// Add families that can be seated in available rows (each row can seat 2 families).
ans += availableRows * 2;
return ans;
}
public static void main(String[] args) {
// Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
int n = 3;
List<List<Integer>> reservedSeats = Arrays.asList(
Arrays.asList(1, 2),
Arrays.asList(1, 3),
Arrays.asList(1, 8),
Arrays.asList(2, 6),
Arrays.asList(3, 1),
Arrays.asList(3, 10)
);
int maxFamilies = maxNumberOfFamilies(n, reservedSeats);
System.out.println("Maximum number of families that can be seated: " + maxFamilies);
}
}
from collections import defaultdict
from bisect import bisect_left
def maxNumberOfFamilies(n, reservedSeats):
# Create a dictionary to store reserved seats for each row.
mp = defaultdict(list)
for seat in reservedSeats:
mp[seat[0]].append(seat[1])
# Variable to store the total number of families
ans = 0
# Rows with all seats vacant
availableRows = n - len(mp)
# Iterate through each row with reserved seats.
for seats in mp.values():
# Sort reserved seats in ascending order.
seats.sort()
# Start checking from seat 2
seat = 2
while seat <= 6:
# Find the first reserved seat that is at least
# 4 positions away from the current seat.
index = bisect_left(seats, seat)
if index == len(seats) or seats[index] - seat >= 4:
ans += 1
# Move to the next possible family seat
seat += 4
else:
# Move to the next seat
seat += 2
# Add families that can be seated in available rows
# (each row can seat 2 families).
ans += availableRows * 2
return ans
n = 3
reservedSeats = [[1, 2], [1, 3], [1, 8], [2, 6], [3, 1], [3, 10]]
maxFamilies = maxNumberOfFamilies(n, reservedSeats)
print("Maximum number of families that can be seated: ", maxFamilies)
function maxNumberOfFamilies(n, reservedSeats) {
// Create a map to store reserved seats for each row.
const seatMap = new Map();
for (const seat of reservedSeats) {
const [row, col] = seat;
if (!seatMap.has(row)) {
seatMap.set(row, new Set());
}
seatMap.get(row).add(col);
}
// Variable to store the total number of families
let ans = 0;
// Rows with all seats vacant
const availableRows = n - seatMap.size;
// Iterate through each row with reserved seats.
for (const [row, seats] of seatMap.entries()) {
// Check all possible groups of 4 seats in this row
let leftGroup = true, middleGroup = true, rightGroup = true;
for (const seat of seats) {
if (seat >= 2 && seat <= 5) {
leftGroup = false;
}
if (seat >= 4 && seat <= 7) {
middleGroup = false;
}
if (seat >= 6 && seat <= 9) {
rightGroup = false;
}
}
// Count families that can be seated in this row
if (leftGroup) {
ans++;
}
if (rightGroup) {
ans++;
}
if (!leftGroup && !rightGroup && middleGroup) {
ans++;
}
}
// Add families that can be seated in available rows
// (each row can seat 2 families).
ans += availableRows * 2;
return ans;
}
// Example usage:
const n1 = 3;
const reservedSeats1 = [[1, 2], [1, 3], [1, 8], [2, 6], [3, 1], [3, 10]];
const maxFamilies1 = maxNumberOfFamilies(n1, reservedSeats1);
console.log("Maximum number of families that can be seated:", maxFamilies1);
Output
Maximum number of families that can be seated: 4
Time complexity: O(n log m), where n is the number of reserved seats and m is the number of rows.
Auxiliary Space: O(n), as we use a hash map to store the reserved seats.