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

Build a segment tree where each node stores the maximum and sum of available seats in its range.
For gather(k, maxRow), find the first row ≤ maxRow with at least k consecutive seats, allocate them, and update the tree.
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.
Both operations run in O(log n) time per query.

Code

[{"language":"C++","code":"class BookMyShow {\n    int n, m;\n    vector<int> seats, maxs, sums;\n    void build(int o, int l, int r) {\n        if (l == r) {\n            maxs[o] = m;\n            sums[o] = m;\n        } else {\n            int mid = (l + r) / 2;\n            build(o*2, l, mid);\n            build(o*2+1, mid+1, r);\n            maxs[o] = m;\n            sums[o] = (r-l+1)*m;\n        }\n    }\n    void update(int o, int l, int r, int idx, int val) {\n        if (l == r) {\n            maxs[o] -= val;\n            sums[o] -= val;\n        } else {\n            int mid = (l + r) / 2;\n            if (idx <= mid) update(o*2, l, mid, idx, val);\n            else update(o*2+1, mid+1, r, idx, val);\n            maxs[o] = max(maxs[o*2], maxs[o*2+1]);\n            sums[o] = sums[o*2] + sums[o*2+1];\n        }\n    }\n    int queryMax(int o, int l, int r, int ql, int qr) {\n        if (ql > r || qr < l) return 0;\n        if (ql <= l && r <= qr) return maxs[o];\n        int mid = (l + r) / 2;\n        return max(queryMax(o*2, l, mid, ql, qr), queryMax(o*2+1, mid+1, r, ql, qr));\n    }\n    int querySum(int o, int l, int r, int ql, int qr) {\n        if (ql > r || qr < l) return 0;\n        if (ql <= l && r <= qr) return sums[o];\n        int mid = (l + r) / 2;\n        return querySum(o*2, l, mid, ql, qr) + querySum(o*2+1, mid+1, r, ql, qr);\n    }\n    int findRow(int o, int l, int r, int ql, int qr, int k) {\n        if (ql > r || qr < l || maxs[o] < k) return -1;\n        if (l == r) return l;\n        int mid = (l + r) / 2;\n        int res = findRow(o*2, l, mid, ql, qr, k);\n        if (res != -1) return res;\n        return findRow(o*2+1, mid+1, r, ql, qr, k);\n    }\npublic:\n    BookMyShow(int n, int m) : n(n), m(m), seats(n, m), maxs(4*n), sums(4*n) {\n        build(1, 0, n-1);\n    }\n    vector<int> gather(int k, int maxRow) {\n        int row = findRow(1, 0, n-1, 0, maxRow, k);\n        if (row == -1) return {};\n        int seat = m - maxs[1 + (row << 2)];\n        update(1, 0, n-1, row, k);\n        return {row, seat};\n    }\n    bool scatter(int k, int maxRow) {\n        if (querySum(1, 0, n-1, 0, maxRow) < k) return false;\n        for (int i = 0; i <= maxRow && k > 0; ++i) {\n            int avail = seats[i];\n            int take = min(avail, k);\n            if (take > 0) {\n                update(1, 0, n-1, i, take);\n                seats[i] -= take;\n                k -= take;\n            }\n        }\n        return true;\n    }\n};","lang":"cpp"},{"language":"Python","code":"class BookMyShow:\n    def __init__(self, n: int, m: int):\n        self.n = n\n        self.m = m\n        self.seats = [m] * n\n        self.maxs = [m] * (4 * n)\n        self.sums = [m * (i+1) for i in range(4 * n)]\n\n    def gather(self, k: int, maxRow: int) -> list[int]:\n        for i in range(min(self.n, maxRow+1)):\n            if self.seats[i] >= k:\n                seat = self.m - self.seats[i]\n

Related Tags