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

Booking Concert Tickets in Groups

Difficulty: Hard

Problem Description

A concert hall has n rows numbered from 0 to n - 1, each with m seats, numbered from 0 to m - 1. You need to design a ticketing system that can allocate seats in the following cases:

  • If a group of k spectators can sit together in a row.
  • If every member of a group of k spectators can get a seat. They may or may not sit together.

Note that the spectators are very picky. Hence:

  • They will book seats only if each member of their group can get a seat with row number less than or equal to maxRow. maxRow can vary from group to group.
  • In case there are multiple rows to choose from, the row with the smallest number is chosen. If there are multiple seats to choose in the same row, the seat with the smallest number is chosen.

Implement the BookMyShow class:

  • BookMyShow(int n, int m) Initializes the object with n as number of rows and m as number of seats per row.
  • int[] gather(int k, int maxRow) Returns an array of length 2 denoting the row and seat number (respectively) of the first seat being allocated to the k members of the group, who must sit together. In other words, it returns the smallest possible r and c such that all [c, c + k - 1] seats are valid and empty in row r, and r <= maxRow. Returns [] in case it is not possible to allocate seats to the group.
  • boolean scatter(int k, int maxRow) Returns true if all k members of the group can be allocated seats in rows 0 to maxRow, who may or may not sit together. If the seats can be allocated, it allocates k seats to the group with the smallest row numbers, and the smallest possible seat numbers in each row. Otherwise, returns false.

Key Insights

  • Efficient seat allocation is crucial due to constraints on n, m, and k.
  • The gather method requires finding continuous empty seats in a row.
  • The scatter method requires distributing seats across multiple rows.
  • Use of data structures that allow quick access to seat availability is essential.

Space and Time Complexity

Time Complexity:

  • gather: O(m) in the worst case where we search through a row for k contiguous seats.
  • scatter: O(n * m) in the worst case if we need to check all rows. Space Complexity:
  • O(n) for maintaining the state of seat availability.

Solution

To tackle this problem, we can use a 2D list (array) to represent the seating arrangement of the concert hall where each element indicates whether a seat is occupied or empty. The gather function will iterate through the rows up to maxRow, checking for k consecutive empty seats. The scatter function will iterate through rows up to maxRow, allocating seats one by one until k seats are taken or we run out of available seats.

Code Solutions

class BookMyShow:
    def __init__(self, n: int, m: int):
        self.n = n  # number of rows
        self.m = m  # number of seats per row
        self.seats = [[0] * m for _ in range(n)]  # 0 means empty, 1 means occupied

    def gather(self, k: int, maxRow: int) -> List[int]:
        for r in range(min(maxRow + 1, self.n)):
            for c in range(self.m - k + 1):
                if all(self.seats[r][c + i] == 0 for i in range(k)):  # check for k consecutive seats
                    for i in range(k):
                        self.seats[r][c + i] = 1  # mark seats as occupied
                    return [r, c]
        return []

    def scatter(self, k: int, maxRow: int) -> bool:
        seats_needed = k
        for r in range(min(maxRow + 1, self.n)):
            for c in range(self.m):
                if self.seats[r][c] == 0:  # find an empty seat
                    self.seats[r][c] = 1  # mark as occupied
                    seats_needed -= 1
                    if seats_needed == 0:
                        return True
        return seats_needed == 0  # return true if all seats are allocated
← Back to All Questions