##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2286.html

# 2286. Booking Concert Tickets in Groups

• Difficulty: Hard.
• Related Topics: Binary Search, Design, Binary Indexed Tree, Segment Tree.
• Similar Questions: Cinema Seat Allocation.

## 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.

Example 1:

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 * 104

• 1 <= m, k <= 109

• 0 <= maxRow <= n - 1

• At most 5 * 104 calls in total will be made to gather and scatter.

## Solution

• class BookMyShow {
private final int n;
private final int m;
// max number of seats in a row for some segment of the rows
private final int[] max;
// total number of seats for some segment of the rows
private final long[] total;
// number of rows with zero free places on the left and on the right
// using this to quickly skip already zero rows
// actual nodes are placed in [1,this.n], the first and last element only shows there the first
// non-zero row
private final int[] numZerosRight;
private final int[] numZerosLeft;

public BookMyShow(int n, int m) {
// make n to be a power of 2 (for simplicity)
this.n = nextPow2(n);
this.m = m;
// segment tree for max number of seats in a row
this.max = new int[this.n * 2 - 1];
// total number of seats for a segment of the rows
this.total = new long[this.n * 2 - 1];
this.numZerosRight = new int[this.n + 2];
this.numZerosLeft = new int[this.n + 2];
// initialize max and total, for max we firstly set values to m
// segments of size 1 are placed starting from this.n - 1
Arrays.fill(max, this.n - 1, this.n + n - 1, m);
Arrays.fill(total, this.n - 1, this.n + n - 1, m);
// calculate values of max and total for segments based on values of their children
for (int i = this.n - 2, i1 = i * 2 + 1, i2 = i * 2 + 2; i >= 0; i--, i1 -= 2, i2 -= 2) {
max[i] = Math.max(max[i1], max[i2]);
total[i] = total[i1] + total[i2];
}
}

public int[] gather(int k, int maxRow) {
// find most left row with enough free places
int mostLeft = mostLeft(0, 0, n, k, maxRow + 1);
if (mostLeft == -1) {
return new int[0];
}
// get corresponding segment tree node
int v = n - 1 + mostLeft;
int[] ans = {mostLeft, m - max[v]};
// update max and total for this node
max[v] -= k;
total[v] -= k;
// until this is a root of segment tree we update its parent
while (v != 0) {
v = (v - 1) / 2;
max[v] = Math.max(max[v * 2 + 1], max[v * 2 + 2]);
total[v] = total[v * 2 + 1] + total[v * 2 + 2];
}
return ans;
}

private int mostLeft(int v, int l, int r, int k, int qr) {
if (l >= qr || max[v] < k) {
return -1;
}
if (l == r - 1) {
return l;
}
int mid = (l + r) / 2;
int left = mostLeft(v * 2 + 1, l, mid, k, qr);
if (left != -1) {
return left;
}
return mostLeft(v * 2 + 2, mid, r, k, qr);
}

public boolean scatter(int k, int maxRow) {
// find total number of free places in the rows [0; maxRow+1)
long sum = total(0, 0, n, maxRow + 1);
if (sum < k) {
return false;
}
int i = 0;
// to don't update parent for both of its children we use a queue
Deque<Integer> deque = new ArrayDeque<>();
while (k != 0) {
i = i + numZerosRight[i] + 1;
int v = n - 1 + i - 1;
int spent = Math.min(k, max[v]);
k -= spent;
max[v] -= spent;
total[v] -= spent;
if (max[v] == 0) {
// update numZerosRight and numZerosLeft
numZerosRight[i - numZerosLeft[i] - 1] += numZerosRight[i] + 1;
numZerosLeft[i + numZerosRight[i] + 1] += numZerosLeft[i] + 1;
}
if (v != 0) {
v = (v - 1) / 2;
// if we already have the parent node in the queue we don't need to update it
if (deque.isEmpty() || deque.peekLast() != v) {
}
}
}
// update max and total
while (!deque.isEmpty()) {
int v = deque.pollFirst();
max[v] = Math.max(max[v * 2 + 1], max[v * 2 + 2]);
total[v] = total[v * 2 + 1] + total[v * 2 + 2];
if (v != 0) {
v = (v - 1) / 2;
// if we already have the parent node in the queue we don't need to update it
if (deque.isEmpty() || deque.peekLast() != v) {
}
}
}
return true;
}

// find sum of [ql, qr)
private long total(int v, int l, int r, int qr) {
if (l >= qr) {
return 0;
}
if (r <= qr) {
}
int mid = (l + r) / 2;
return total(v * 2 + 1, l, mid, qr) + total(v * 2 + 2, mid, r, qr);
}

private static int nextPow2(int n) {
if ((n & (n - 1)) == 0) {
return n;
}
return Integer.highestOneBit(n) << 1;
}
}

/**
* Your BookMyShow object will be instantiated and called as such:
* BookMyShow obj = new BookMyShow(n, m);
* int[] param_1 = obj.gather(k,maxRow);
* boolean param_2 = obj.scatter(k,maxRow);
*/

############

class Node {
int l, r;
long mx, s;
}

class SegmentTree {
private Node[] tr;
private int m;

public SegmentTree(int n, int m) {
this.m = m;
tr = new Node[n << 2];
for (int i = 0; i < tr.length; ++i) {
tr[i] = new Node();
}
build(1, 1, n);
}

private void build(int u, int l, int r) {
tr[u].l = l;
tr[u].r = r;
if (l == r) {
tr[u].s = m;
tr[u].mx = m;
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}

public void modify(int u, int x, long v) {
if (tr[u].l == x && tr[u].r == x) {
tr[u].s = v;
tr[u].mx = v;
return;
}
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid) {
modify(u << 1, x, v);
} else {
modify(u << 1 | 1, x, v);
}
pushup(u);
}

public long querySum(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) {
return tr[u].s;
}
int mid = (tr[u].l + tr[u].r) >> 1;
long v = 0;
if (l <= mid) {
v += querySum(u << 1, l, r);
}
if (r > mid) {
v += querySum(u << 1 | 1, l, r);
}
return v;
}

public int queryIdx(int u, int l, int r, int k) {
if (tr[u].mx < k) {
return 0;
}
if (tr[u].l == tr[u].r) {
return tr[u].l;
}
int mid = (tr[u].l + tr[u].r) >> 1;
if (tr[u << 1].mx >= k) {
return queryIdx(u << 1, l, r, k);
}
if (r > mid) {
return queryIdx(u << 1 | 1, l, r, k);
}
return 0;
}

private void pushup(int u) {
tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
tr[u].mx = Math.max(tr[u << 1].mx, tr[u << 1 | 1].mx);
}
}

class BookMyShow {
private int n;
private int m;
private SegmentTree tree;

public BookMyShow(int n, int m) {
this.n = n;
this.m = m;
tree = new SegmentTree(n, m);
}

public int[] gather(int k, int maxRow) {
++maxRow;
int i = tree.queryIdx(1, 1, maxRow, k);
if (i == 0) {
return new int[] {};
}
long s = tree.querySum(1, i, i);
tree.modify(1, i, s - k);
return new int[] {i - 1, (int) (m - s)};
}

public boolean scatter(int k, int maxRow) {
++maxRow;
if (tree.querySum(1, 1, maxRow) < k) {
return false;
}
int i = tree.queryIdx(1, 1, maxRow, 1);
for (int j = i; j <= n; ++j) {
long s = tree.querySum(1, j, j);
if (s >= k) {
tree.modify(1, j, s - k);
return true;
}
k -= s;
tree.modify(1, j, 0);
}
return true;
}
}

/**
* Your BookMyShow object will be instantiated and called as such:
* BookMyShow obj = new BookMyShow(n, m);
* int[] param_1 = obj.gather(k,maxRow);
* boolean param_2 = obj.scatter(k,maxRow);
*/

• class Node:
def __init__(self):
self.l = self.r = 0
self.s = self.mx = 0

class SegmentTree:
def __init__(self, n, m):
self.m = m
self.tr = [Node() for _ in range(n << 2)]
self.build(1, 1, n)

def build(self, u, l, r):
self.tr[u].l, self.tr[u].r = l, r
if l == r:
self.tr[u].s = self.tr[u].mx = self.m
return
mid = (l + r) >> 1
self.build(u << 1, l, mid)
self.build(u << 1 | 1, mid + 1, r)
self.pushup(u)

def modify(self, u, x, v):
if self.tr[u].l == x and self.tr[u].r == x:
self.tr[u].s = self.tr[u].mx = v
return
mid = (self.tr[u].l + self.tr[u].r) >> 1
if x <= mid:
self.modify(u << 1, x, v)
else:
self.modify(u << 1 | 1, x, v)
self.pushup(u)

def query_sum(self, u, l, r):
if self.tr[u].l >= l and self.tr[u].r <= r:
return self.tr[u].s
mid = (self.tr[u].l + self.tr[u].r) >> 1
v = 0
if l <= mid:
v += self.query_sum(u << 1, l, r)
if r > mid:
v += self.query_sum(u << 1 | 1, l, r)
return v

def query_idx(self, u, l, r, k):
if self.tr[u].mx < k:
return 0
if self.tr[u].l == self.tr[u].r:
return self.tr[u].l
mid = (self.tr[u].l + self.tr[u].r) >> 1
if self.tr[u << 1].mx >= k:
return self.query_idx(u << 1, l, r, k)
if r > mid:
return self.query_idx(u << 1 | 1, l, r, k)
return 0

def pushup(self, u):
self.tr[u].s = self.tr[u << 1].s + self.tr[u << 1 | 1].s
self.tr[u].mx = max(self.tr[u << 1].mx, self.tr[u << 1 | 1].mx)

class BookMyShow:
def __init__(self, n: int, m: int):
self.n = n
self.tree = SegmentTree(n, m)

def gather(self, k: int, maxRow: int) -> List[int]:
maxRow += 1
i = self.tree.query_idx(1, 1, maxRow, k)
if i == 0:
return []
s = self.tree.query_sum(1, i, i)
self.tree.modify(1, i, s - k)
return [i - 1, self.tree.m - s]

def scatter(self, k: int, maxRow: int) -> bool:
maxRow += 1
if self.tree.query_sum(1, 1, maxRow) < k:
return False
i = self.tree.query_idx(1, 1, maxRow, 1)
for j in range(i, self.n + 1):
s = self.tree.query_sum(1, j, j)
if s >= k:
self.tree.modify(1, j, s - k)
return True
k -= s
self.tree.modify(1, j, 0)
return True

# Your BookMyShow object will be instantiated and called as such:
# obj = BookMyShow(n, m)
# param_1 = obj.gather(k,maxRow)
# param_2 = obj.scatter(k,maxRow)

############

# 2286. Booking Concert Tickets in Groups
# https://leetcode.com/problems/booking-concert-tickets-in-groups

class Node:
def __init__(self, start, end):
self.left = None
self.right = None
self.start = start
self.end = end
self.total = 0
self.mx = 0

class SegTree:

def __init__(self, n, val):
self.root = self.buildTree(0, n, val)

def buildTree(self, start, end, val):
if start > end: return None

if start == end:
node = Node(start, end)
node.total = val
node.mx = val

return node

node = Node(start, end)
mid = start + (end - start) // 2
node.left = self.buildTree(start, mid, val)
node.right = self.buildTree(mid + 1, end, val)
node.total = node.left.total + node.right.total
node.mx = max(node.left.mx, node.right.mx)

return node

def update(self, index: int, val: int) -> None:
self.updateR(self.root, index, val)

def updateR(self, node, index, val):

if node.start == node.end:
node.total -= val
node.mx -= val
else:
mid = node.start + (node.end - node.start) // 2
if index <= mid:
self.updateR(node.left, index, val)
else:
self.updateR(node.right, index, val)

node.total = node.left.total + node.right.total
node.mx = max(node.left.mx, node.right.mx)

def sumRange(self, left: int, right: int) -> int:
return self.sumRangeR(self.root, left, right)

def sumRangeR(self, node, left, right):
if not node or node.start > right or node.end < left: return 0

if node.start >= left and node.end <= right: return node.total

l = self.sumRangeR(node.left, left, right)
r = self.sumRangeR(node.right, left, right)

return l + r

def maxQuery(self, k, maxRow, seats):

def maxQueryHelper(node):
if node.start == node.end:
if node.end > maxRow or node.total < k:
return []

if node.end <= maxRow and node.total >= k:
return [node.end, seats - node.total]

return maxQueryHelper(node.left) if node.left.mx >= k else maxQueryHelper(node.right)

return maxQueryHelper(self.root)

class BookMyShow:

def __init__(self, n: int, m: int):
self.seg = SegTree(n - 1, m)
self.seats = [m] * n
self.m = m
self.n = n
self.startRow = 0

def gather(self, k: int, maxRow: int) -> List[int]:
res = self.seg.maxQuery(k, maxRow, self.m)

if res:
row = res[0]
self.seg.update(row, k)
self.seats[row] -= k

return res

def scatter(self, k: int, maxRow: int) -> bool:
if self.seg.sumRange(0, maxRow) < k:
return False

index = self.startRow
curr = 0

while curr < k:
rest = k - curr

if rest >= self.seats[index]:
self.seg.update(index, self.seats[index])
curr += self.seats[index]
self.seats[index] = 0
index += 1
self.startRow = index
else:
self.seg.update(index, rest)
self.seats[index] -= rest
curr += rest

return True

# Your BookMyShow object will be instantiated and called as such:
# obj = BookMyShow(n, m)
# param_1 = obj.gather(k,maxRow)
# param_2 = obj.scatter(k,maxRow)


• class Node {
public:
int l, r;
long s, mx;
};

class SegmentTree {
public:
SegmentTree(int n, int m) {
this->m = m;
tr.resize(n << 2);
for (int i = 0; i < n << 2; ++i) {
tr[i] = new Node();
}
build(1, 1, n);
}

void modify(int u, int x, int v) {
if (tr[u]->l == x && tr[u]->r == x) {
tr[u]->s = tr[u]->mx = v;
return;
}
int mid = (tr[u]->l + tr[u]->r) >> 1;
if (x <= mid) {
modify(u << 1, x, v);
} else {
modify(u << 1 | 1, x, v);
}
pushup(u);
}

long querySum(int u, int l, int r) {
if (tr[u]->l >= l && tr[u]->r <= r) {
return tr[u]->s;
}
int mid = (tr[u]->l + tr[u]->r) >> 1;
long v = 0;
if (l <= mid) {
v += querySum(u << 1, l, r);
}
if (r > mid) {
v += querySum(u << 1 | 1, l, r);
}
return v;
}

int queryIdx(int u, int l, int r, int k) {
if (tr[u]->mx < k) {
return 0;
}
if (tr[u]->l == tr[u]->r) {
return tr[u]->l;
}
int mid = (tr[u]->l + tr[u]->r) >> 1;
if (tr[u << 1]->mx >= k) {
return queryIdx(u << 1, l, r, k);
}
if (r > mid) {
return queryIdx(u << 1 | 1, l, r, k);
}
return 0;
}

private:
vector<Node*> tr;
int m;

void build(int u, int l, int r) {
tr[u]->l = l;
tr[u]->r = r;
if (l == r) {
tr[u]->s = m;
tr[u]->mx = m;
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}

void pushup(int u) {
tr[u]->s = tr[u << 1]->s + tr[u << 1 | 1]->s;
tr[u]->mx = max(tr[u << 1]->mx, tr[u << 1 | 1]->mx);
}
};

class BookMyShow {
public:
BookMyShow(int n, int m) {
this->n = n;
this->m = m;
tree = new SegmentTree(n, m);
}

vector<int> gather(int k, int maxRow) {
++maxRow;
int i = tree->queryIdx(1, 1, maxRow, k);
if (i == 0) {
return {};
}
long s = tree->querySum(1, i, i);
tree->modify(1, i, s - k);
return {i - 1, (int) (m - s)};
}

bool scatter(int k, int maxRow) {
++maxRow;
if (tree->querySum(1, 1, maxRow) < k) {
return false;
}
int i = tree->queryIdx(1, 1, maxRow, 1);
for (int j = i; j <= n; ++j) {
long s = tree->querySum(1, j, j);
if (s >= k) {
tree->modify(1, j, s - k);
return true;
}
k -= s;
tree->modify(1, j, 0);
}
return true;
}

private:
SegmentTree* tree;
int m, n;
};

/**
* Your BookMyShow object will be instantiated and called as such:
* BookMyShow* obj = new BookMyShow(n, m);
* vector<int> param_1 = obj->gather(k,maxRow);
* bool param_2 = obj->scatter(k,maxRow);
*/

• type BookMyShow struct {
n, m int
tree *segmentTree
}

func Constructor(n int, m int) BookMyShow {
return BookMyShow{n, m, newSegmentTree(n, m)}
}

func (this *BookMyShow) Gather(k int, maxRow int) []int {
maxRow++
i := this.tree.queryIdx(1, 1, maxRow, k)
if i == 0 {
return []int{}
}
s := this.tree.querySum(1, i, i)
this.tree.modify(1, i, s-k)
return []int{i - 1, this.m - s}
}

func (this *BookMyShow) Scatter(k int, maxRow int) bool {
maxRow++
if this.tree.querySum(1, 1, maxRow) < k {
return false
}
i := this.tree.queryIdx(1, 1, maxRow, 1)
for j := i; j <= this.n; j++ {
s := this.tree.querySum(1, j, j)
if s >= k {
this.tree.modify(1, j, s-k)
return true
}
k -= s
this.tree.modify(1, j, 0)
}
return true
}

type node struct {
l, r, s, mx int
}

type segmentTree struct {
tr []*node
m  int
}

func newSegmentTree(n, m int) *segmentTree {
tr := make([]*node, n<<2)
for i := range tr {
tr[i] = &node{}
}
t := &segmentTree{tr, m}
t.build(1, 1, n)
return t
}

func (t *segmentTree) build(u, l, r int) {
t.tr[u].l, t.tr[u].r = l, r
if l == r {
t.tr[u].s, t.tr[u].mx = t.m, t.m
return
}
mid := (l + r) >> 1
t.build(u<<1, l, mid)
t.build(u<<1|1, mid+1, r)
t.pushup(u)
}

func (t *segmentTree) modify(u, x, v int) {
if t.tr[u].l == x && t.tr[u].r == x {
t.tr[u].s, t.tr[u].mx = v, v
return
}
mid := (t.tr[u].l + t.tr[u].r) >> 1
if x <= mid {
t.modify(u<<1, x, v)
} else {
t.modify(u<<1|1, x, v)
}
t.pushup(u)
}

func (t *segmentTree) querySum(u, l, r int) int {
if t.tr[u].l >= l && t.tr[u].r <= r {
return t.tr[u].s
}
mid := (t.tr[u].l + t.tr[u].r) >> 1
v := 0
if l <= mid {
v = t.querySum(u<<1, l, r)
}
if r > mid {
v += t.querySum(u<<1|1, l, r)
}
return v
}

func (t *segmentTree) queryIdx(u, l, r, k int) int {
if t.tr[u].mx < k {
return 0
}
if t.tr[u].l == t.tr[u].r {
return t.tr[u].l
}
mid := (t.tr[u].l + t.tr[u].r) >> 1
if t.tr[u<<1].mx >= k {
return t.queryIdx(u<<1, l, r, k)
}
if r > mid {
return t.queryIdx(u<<1|1, l, r, k)
}
return 0
}

func (t *segmentTree) pushup(u int) {
t.tr[u].s = t.tr[u<<1].s + t.tr[u<<1|1].s
t.tr[u].mx = max(t.tr[u<<1].mx, t.tr[u<<1|1].mx)
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

/**
* Your BookMyShow object will be instantiated and called as such:
* obj := Constructor(n, m);
* param_1 := obj.Gather(k,maxRow);
* param_2 := obj.Scatter(k,maxRow);
*/


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).