Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

**Input**
["BookMyShow", "gather", "gather", "scatter", "scatter"]
[[2, 5], [4, 0], [2, 0], [5, 1], [5, 1]]
**Output**
[null, [0, 0], [], true, false]

**Explanation**
BookMyShow bms = new BookMyShow(2, 5); // There are 2 rows with 5 seats each 
bms.gather(4, 0); // return [0, 0]
                  // The group books seats [0, 3] of row 0. 
bms.gather(2, 0); // return []
                  // There is only 1 seat left in row 0,
                  // so it is not possible to book 2 consecutive seats. 
bms.scatter(5, 1); // return True
                   // The group books seat 4 of row 0 and seats [0, 3] of row 1. 
bms.scatter(5, 1); // return False
                   // There is only one seat left in the hall.

Constraints

  • 1 <= n <= 5 * 10^4
  • 1 <= m, k <= 10^9
  • 0 <= maxRow <= n - 1
  • At most 5 * 10^4 calls in total will be made to gather and scatter.

Solution

Method 1 – Segment Tree for Range Maximum and Sum

Intuition

To efficiently support group bookings (together or scattered) and queries for available seats, we use a segment tree to maintain the maximum and sum of available seats in each row. This allows us to quickly find the first row with enough seats and update seat counts after booking.

Approach

  1. Build a segment tree where each node stores the maximum and sum of available seats in its range.
  2. For gather(k, maxRow), find the first row ≤ maxRow with at least k consecutive seats, allocate them, and update the tree.
  3. For scatter(k, maxRow), check if the total available seats in rows ≤ maxRow is at least k, then allocate seats greedily from the lowest row and update the tree.
  4. Both operations run in O(log n) time per query.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

class BookMyShow {
    int n, m;
    vector<int> seats, maxs, sums;
    void build(int o, int l, int r) {
        if (l == r) {
            maxs[o] = m;
            sums[o] = m;
        } else {
            int mid = (l + r) / 2;
            build(o*2, l, mid);
            build(o*2+1, mid+1, r);
            maxs[o] = m;
            sums[o] = (r-l+1)*m;
        }
    }
    void update(int o, int l, int r, int idx, int val) {
        if (l == r) {
            maxs[o] -= val;
            sums[o] -= val;
        } else {
            int mid = (l + r) / 2;
            if (idx <= mid) update(o*2, l, mid, idx, val);
            else update(o*2+1, mid+1, r, idx, val);
            maxs[o] = max(maxs[o*2], maxs[o*2+1]);
            sums[o] = sums[o*2] + sums[o*2+1];
        }
    }
    int queryMax(int o, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return 0;
        if (ql <= l && r <= qr) return maxs[o];
        int mid = (l + r) / 2;
        return max(queryMax(o*2, l, mid, ql, qr), queryMax(o*2+1, mid+1, r, ql, qr));
    }
    int querySum(int o, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return 0;
        if (ql <= l && r <= qr) return sums[o];
        int mid = (l + r) / 2;
        return querySum(o*2, l, mid, ql, qr) + querySum(o*2+1, mid+1, r, ql, qr);
    }
    int findRow(int o, int l, int r, int ql, int qr, int k) {
        if (ql > r || qr < l || maxs[o] < k) return -1;
        if (l == r) return l;
        int mid = (l + r) / 2;
        int res = findRow(o*2, l, mid, ql, qr, k);
        if (res != -1) return res;
        return findRow(o*2+1, mid+1, r, ql, qr, k);
    }
public:
    BookMyShow(int n, int m) : n(n), m(m), seats(n, m), maxs(4*n), sums(4*n) {
        build(1, 0, n-1);
    }
    vector<int> gather(int k, int maxRow) {
        int row = findRow(1, 0, n-1, 0, maxRow, k);
        if (row == -1) return {};
        int seat = m - maxs[1 + (row << 2)];
        update(1, 0, n-1, row, k);
        return {row, seat};
    }
    bool scatter(int k, int maxRow) {
        if (querySum(1, 0, n-1, 0, maxRow) < k) return false;
        for (int i = 0; i <= maxRow && k > 0; ++i) {
            int avail = seats[i];
            int take = min(avail, k);
            if (take > 0) {
                update(1, 0, n-1, i, take);
                seats[i] -= take;
                k -= take;
            }
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class BookMyShow:
    def __init__(self, n: int, m: int):
        self.n = n
        self.m = m
        self.seats = [m] * n
        self.maxs = [m] * (4 * n)
        self.sums = [m * (i+1) for i in range(4 * n)]

    def gather(self, k: int, maxRow: int) -> list[int]:
        for i in range(min(self.n, maxRow+1)):
            if self.seats[i] >= k:
                seat = self.m - self.seats[i]
                self.seats[i] -= k
                return [i, seat]
        return []

    def scatter(self, k: int, maxRow: int) -> bool:
        total = sum(self.seats[:maxRow+1])
        if total < k:
            return False
        for i in range(min(self.n, maxRow+1)):
            take = min(self.seats[i], k)
            self.seats[i] -= take
            k -= take
            if k == 0:
                break
        return True

Complexity

  • ⏰ Time complexity: O(log n) per query for segment tree, O(n) for simple array (Python version).
  • 🧺 Space complexity: O(n) — For seat tracking arrays.