LeetCode Solutions Blog

Booking Concert Tickets in Groups

Number: 2380

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Design a ticket booking system for a concert hall with n rows and m seats per row. The system must support two operations:

gather(k, maxRow): Allocate k consecutive seats in a single row (with row index ≤ maxRow) and return the row and starting seat index if possible.
scatter(k, maxRow): Allocate k seats (not necessarily consecutive) among rows 0 to maxRow, using seats in the smallest rows and leftmost positions available.
If allocation is not possible, return an empty result (for gather) or false (for scatter).

Key Insights

Each row can be viewed as having a contiguous block of available seats starting from a pointer (initially 0) because seats are allocated from left to right.
For gather queries, we need to quickly find the first row (≤ maxRow) that has at least k consecutive available seats; this can be done by maintaining a segment tree (or BIT) that tracks the maximum contiguous seats per row.
For scatter queries, we require the total sum of available seats in rows [0, maxRow] to be at least k; if so, we then allocate seats row by row.
A segment tree is ideal since it can support both range maximum queries (for gather) and range sum queries (for scatter) with efficient point updates.
The allocation order (smallest row and seat number) is naturally maintained if each row allocates from its leftmost available seat.

Space and Time Complexity

Time Complexity: Each gather or scatter call performs O(log n) work per segment tree query/update (gather uses binary-search on the tree, and scatter may update several rows but overall remains efficient given constraints).
Space Complexity: O(n) for maintaining the segment tree and auxiliary arrays.

Solution

The solution maintains an array where each entry indicates the number of available consecutive seats in that row (initially m for every row). A segment tree is built on top of this array providing two capabilities:

Query the maximum available seats in any row for a given range (to support gather).
Query the total sum of available seats in any range (to support scatter).

For a gather(k, maxRow) call, the segment tree is queried over the range [0, maxRow] to check if any row has at least k available consecutive seats. If found, a binary search over the segment tree identifies the earliest row with this property. The starting seat in that row is computed as m minus the current available seats, and the row’s available count is decremented by k followed by an update in the segment tree.

For a scatter(k, maxRow) call, the segment tree is queried for the total available seats in the range [0, maxRow]. If the sum is at least k, allocation proceeds row by row—each row contributes as many seats as it can (from its leftmost available seat), updating the segment tree accordingly, until k seats have been allocated.

Code Solutions

# Python solution using a segment tree

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        # tree stores tuple (sum, max) for segment
        self.tree = [None] * (4 * self.n)
        self.build(arr, 0, 0, self.n - 1)
    
    def build(self, arr, idx, left, right):
        if left == right:
            self.tree[idx] = (arr[left], arr[left])  # (sum, max)
            return
        mid = (left + right) // 2
        self.build(arr, 2 * idx + 1, left, mid)
        self.build(arr, 2 * idx + 2, mid + 1, right)
        self.tree[idx] = (self.tree[2 * idx + 1][0] + self.tree[2 * idx + 2][0],
                          max(self.tree[2 * idx + 1][1], self.tree[2 * idx + 2][1]))
    
    def update(self, pos, value, idx, left, right):
        if left == right:
            self.tree[idx] = (value, value)
            return
        mid = (left + right) // 2
        if pos <= mid:
            self.update(pos, value, 2 * idx + 1, left, mid)
        else:
            self.update(pos, value, 2 * idx + 2, mid + 1, right)
        self.tree[idx] = (self.tree[2 * idx + 1][0] + self.tree[2 * idx + 2][0],
                          max(self.tree[2 * idx + 1][1], self.tree[2 * idx + 2][1]))
    
    def query_sum(self, ql, qr, idx, left, right):
        if ql > right or qr < left:
            return 0
        if ql <= left and right <= qr:
            return self.tree[idx][0]
        mid = (left + right) // 2
        return self.query_sum(ql, qr, 2 * idx + 1, left, mid) + \
               self.query_sum(ql, qr, 2 * idx + 2, mid + 1, right)
    
    def query_max(self, ql, qr, idx, left, right):
        if ql > right or qr < left:
            return -1
        if ql <= left and right <= qr:
            return self.tree[idx][1]
        mid = (left + right) // 2
        return max(self.query_max(ql, qr, 2 * idx + 1, left, mid),
                   self.query_max(ql, qr, 2 * idx + 2, mid + 1, right))
    
    # Binary search on the tree to get the first index with value >= k in range [ql, qr]
    def find_first(self, ql, qr, k, idx, left, right):
        if left > qr or right < ql or self.tree[idx][1] < k:
            return -1
        if left == right:
            return left
        mid = (left + right) // 2
        res = self.find_first(ql, qr, k, 2 * idx + 1, left, mid)
        if res == -1:
            res = self.find_first(ql, qr, k, 2 * idx + 2, mid + 1, right)
        return res


class BookMyShow:
    def __init__(self, n: int, m: int):
        self.n = n
        self.m = m
        # For each row, available seats = m initially.
        self.avail = [m] * n
        self.seg = SegmentTree(self.avail)

    def gather(self, k: int, maxRow: int):
        # Query maximum available contiguous seats in range [0, maxRow]
        if self.seg.query_max(0, maxRow, 0, 0, self.n - 1) < k:
            return []  # Not possible
        # Find the first row with available seats >= k
        row = self.seg.find_first(0, maxRow, k, 0, 0, self.n - 1)
        # Calculate starting seat position in this row
        start_seat = self.m - self.avail[row]
        # Update available seats in that row
        self.avail[row] -= k
        self.seg.update(row, self.avail[row], 0, 0, self.n - 1)
        return [row, start_seat]

    def scatter(self, k: int, maxRow: int) -> bool:
        # Check if total available seats in [0, maxRow] is enough.
        total = self.seg.query_sum(0, maxRow, 0, 0, self.n - 1)
        if total < k:
            return False
        # Allocate seats row by row.
        row = 0
        while k > 0 and row <= maxRow:
            if self.avail[row] > 0:
                allocate = min(self.avail[row], k)
                self.avail[row] -= allocate
                self.seg.update(row, self.avail[row], 0, 0, self.n - 1)
                k -= allocate
            row += 1
        return True