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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Cinema Seat Allocation

Difficulty: Medium

Problem Description

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. Given the array reservedSeats containing the numbers of seats 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 are not considered to be adjacent, but there is an exceptional case where an aisle can split a four-person group, allowing two people on each side.

Key Insights

  • Each row has a fixed number of seats (10) which can be categorized into possible configurations for four-person groups.
  • Reserved seats can block certain configurations, so we need to account for these when calculating the maximum groups.
  • There are specific patterns of seat groups:
    • 1-2-3-4
    • 2-3-4-5
    • 3-4-5-6
    • 4-5-6-7
    • 5-6-7-8
    • 6-7-8-9
    • 7-8-9-10
    • A special configuration across the aisle: 2-3-4-6 allows 2 on one side and 2 on the other.

Space and Time Complexity

Time Complexity: O(m) where m is the number of reserved seats. Space Complexity: O(n) where n is the number of rows (though we only need to track reserved seats).

Solution

To solve the problem, we will use a hash table (or dictionary) to keep track of reserved seats in each row. For each row, we will check for the availability of the predefined configurations that can accommodate a four-person group. We will iterate through the reserved seats and mark the reserved seats for each row. Finally, we will count the maximum groups that can fit based on the available configurations.

Code Solutions

def maxNumberOfFamilies(n, reservedSeats):
    reserved = {}
    
    # Mark reserved seats by row
    for row, seat in reservedSeats:
        if row not in reserved:
            reserved[row] = set()
        reserved[row].add(seat)
    
    max_groups = 0
    
    for row in range(1, n + 1):
        if row in reserved:
            seats = reserved[row]
            count = 0
            
            # Check configurations
            if all(seat not in seats for seat in [2, 3, 4, 5]):
                count += 1  # Group (2,3,4,5)
            if all(seat not in seats for seat in [3, 4, 5, 6]):
                count += 1  # Group (3,4,5,6)
            if all(seat not in seats for seat in [4, 5, 6, 7]):
                count += 1  # Group (4,5,6,7)
            if all(seat not in seats for seat in [5, 6, 7, 8]):
                count += 1  # Group (5,6,7,8)
            if all(seat not in seats for seat in [6, 7, 8, 9]):
                count += 1  # Group (6,7,8,9)
            if all(seat not in seats for seat in [7, 8, 9, 10]):
                count += 1  # Group (7,8,9,10)
            
            # Check for split group
            if all(seat not in seats for seat in [2, 3, 4]) and all(seat not in seats for seat in [6, 7, 8]):
                count += 1  # Group (2,3,4 | 6,7,8)
            
            max_groups += count
        else:
            max_groups += 2  # Two full groups in a row if no seats are reserved
            
    return max_groups
← Back to All Questions