We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Cinema Seat Allocation

Number: 1487

Difficulty: Medium

Paid? No

Companies: Microsoft, Google, Zoho

Problem Description

Given a cinema with n rows and 10 seats per row, some seats are reserved. A group of four must sit together in one row, and they can only use seats that are adjacent except when the group is split by the aisle—in which case the group occupies 2 seats on each side of the aisle. The available sets of seats for placing a group are: seats 2-5 (left block), seats 6-9 (right block), or seats 4-7 (middle block, which is used when neither left nor right block is available). The task is to determine the maximum number of groups that can be allocated in the cinema.

Key Insights

  • Rows with no reserved seats can always seat 2 groups.
  • Only rows that have at least one reservation influence the allocation.
  • For a row with reserved seats, check three seat blocks:
    • Left block (seats 2-5)
    • Right block (seats 6-9)
    • Middle block (seats 4-7) as a fallback if neither left nor right block is available.
  • Use a hash map (or dictionary) to store reserved seats per row, limiting processing only to affected rows.
  • The overall answer is the free rows count × 2 plus the count from rows that have reservations.

Space and Time Complexity

Time Complexity: O(m) where m is the number of reserved seats, since we only process rows that have reservations. Space Complexity: O(m) for storing reserved seat information per affected row.

Solution

The solution leverages a hash table to track the reserved seats of each affected row. We first compute the number of rows with reservations and assume that all other rows can fully accommodate 2 groups each. For each reserved row, we check:

  • If seats 2, 3, 4, and 5 are free, mark the left block as available.
  • If seats 6, 7, 8, and 9 are free, mark the right block as available.
  • If neither block is available, then check if the middle block (seats 4-7) is free. Accordingly, we determine the count of groups that can be allocated in that specific row. The final answer is the sum of groups from the reserved rows and the groups from completely free rows.

Code Solutions

# Python solution for Cinema Seat Allocation

def maxNumberOfFamilies(n, reservedSeats):
    # Dictionary to map row -> set of reserved seat numbers in that row
    reserved_map = {}
    
    # Process each reserved seat and map them by row
    for row, seat in reservedSeats:
        if row not in reserved_map:
            reserved_map[row] = set()
        reserved_map[row].add(seat)
    
    # Initialize count with rows that are not in reserved_map
    total_groups = (n - len(reserved_map)) * 2

    # For each row that has reservations, check valid seat blocks
    for row in reserved_map:
        reserved = reserved_map[row]
        count = 0
        # Check if left block (seats 2-5) is free
        if all(seat not in reserved for seat in range(2, 6)):
            count += 1
        # Check if right block (seats 6-9) is free
        if all(seat not in reserved for seat in range(6, 10)):
            count += 1
        # If neither left nor right block is free but middle block (4-7) is free,
        # allow one allocation.
        if count == 0 and all(seat not in reserved for seat in range(4, 8)):
            count = 1
        total_groups += count
    
    return total_groups

# Example usage:
# n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
print(maxNumberOfFamilies(3, [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]))
← Back to All Questions