Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Booking Concert Tickets in Groups LeetCode Solution
Problem – Booking Concert Tickets in Groups leetCode Solution
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
kspectators can sit together in a row. - If every member of a group of
kspectators 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.maxRowcan 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 withnas number of rows andmas number of seats per row.int[] gather(int k, int maxRow)Returns an array of length2denoting the row and seat number (respectively) of the first seat being allocated to thekmembers of the group, who must sit together. In other words, it returns the smallest possiblerandcsuch that all[c, c + k - 1]seats are valid and empty in rowr, andr <= maxRow. Returns[]in case it is not possible to allocate seats to the group.boolean scatter(int k, int maxRow)Returnstrueif allkmembers of the group can be allocated seats in rows0tomaxRow, who may or may not sit together. If the seats can be allocated, it allocateskseats to the group with the smallest row numbers, and the smallest possible seat numbers in each row. Otherwise, returnsfalse.
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 * 1041 <= m, k <= 1090 <= maxRow <= n - 1- At most
5 * 104calls in total will be made togatherandscatter.
Booking Concert Tickets in Groups LeetCode Solution in C++
class BookMyShow {
int n;
int m;
vector<array<long long, 2>> stree; // segment tree that tracks (max, sum) of each segment
public:
void build(int i, int p, int q) {
if (p == q) {
stree[i] = {m, m};
return;
}
int r = (p + q) / 2;
stree[i] = {m, (long long)(q-p+1)*m};
build(2*i+1, p, r);
build(2*i+2, r+1, q);
}
vector<int> query_max(int i, int p, int q, int k, int maxRow) {
if (p > maxRow)
return {};
if (stree[i][0] < k)
return {};
if (p == q)
return {p, (int)(m - stree[i][0])};
int r = (p + q) / 2;
vector<int> ret = query_max(2*i+1, p, r, k, maxRow);
if (ret.size())
return ret;
return query_max(2*i+2, r+1, q, k, maxRow);
}
void update_max(int i, int p, int q, int row, int k) {
if (p > row || q < row)
return;
if (p == q) {
stree[i][0] -= k;
stree[i][1] -= k;
// cout << p << " " << stree[i][0] << endl;
return;
}
int r = (p + q) / 2;
stree[i][1] -= k;
update_max(2*i+1, p, r, row, k);
update_max(2*i+2, r+1, q, row, k);
stree[i][0] = max(stree[2*i+1][0], stree[2*i+2][0]);
}
long long query_sum(int i, int p, int q, int maxRow) {
if (p > maxRow)
return 0;
if (q <= maxRow)
return stree[i][1];
int r = (p + q) / 2;
return query_sum(2*i+1, p, r, maxRow) + query_sum(2*i+2, r+1, q, maxRow);
}
void update_sum(int i, int p, int q, int k, int maxRow) {
if (p > maxRow)
return;
if (p == q) {
stree[i][0] -= k;
stree[i][1] -= k;
// cout << p << " " << stree[i][0] << endl;
return;
}
int r = (p + q) / 2;
stree[i][1] -= k;
if (r+1 > maxRow || stree[2*i+1][1] >= k) {
update_sum(2*i+1, p, r, k, maxRow);
} else {
k -= stree[2*i+1][1];
update_sum(2*i+1, p, r, stree[2*i+1][1], maxRow);
// Be aware: stree[2*i+1][1] updates while updating the left tree
update_sum(2*i+2, r+1, q, k, maxRow);
}
stree[i][0] = max(stree[2*i+1][0], stree[2*i+2][0]);
}
BookMyShow(int n_in, int m_in) {
n = n_in;
m = m_in;
int sz = 1;
while (sz < n*2)
sz <<= 1;
stree.resize(sz);
build(0, 0, n-1);
}
vector<int> gather(int k, int maxRow) {
// cout << "gather " << k << " " << maxRow << endl;
vector<int> ret = query_max(0, 0, n-1, k, maxRow);
if (ret.size())
update_max(0, 0, n-1, ret[0], k);
return ret;
}
bool scatter(int k, int maxRow) {
// cout << "scatter " << k << " " << maxRow << endl;
long long cnt = query_sum(0, 0, n-1, maxRow);
bool ret = cnt >= k;
if (ret)
update_sum(0, 0, n-1, k, maxRow);
return ret;
}
};Booking Concert Tickets in Groups LeetCode Solution in Python
class Node:
def __init__(self, start, end):
self.s = start
self.e = end
self.left = None
self.right = None
self.total = 0 # for range sum query
self.mx = 0 # for range max query
class SegTree:
def __init__(self, start, end, val):
def build(l, r):
if l > r:
return None
if l == r:
node = Node(l, r)
node.total = val
node.mx = val
return node
node = Node(l, r)
m = (l + r) // 2
node.left = build(l, m)
node.right = build(m+1, r)
node.mx = max(node.left.mx, node.right.mx)
node.total = node.left.total + node.right.total
return node
self.root = build(start, end)
# update the total remain seats and the max remain seats for each node (range) in the segment tree
def update(self, index, val):
def updateHelper(node):
if node.s == node.e == index:
node.total -= val
node.mx -= val
return
m = (node.s + node.e) // 2
if index <= m:
updateHelper(node.left)
elif index > m:
updateHelper(node.right)
node.mx = max(node.left.mx, node.right.mx)
node.total = node.left.total + node.right.total
return
updateHelper(self.root)
def maxQuery(self, k, maxRow, seats):
def queryHelper(node):
if node.s == node.e:
# check if the row number is less than maxRow and the number of remains seats is greater or equal than k
if node.e > maxRow or node.total < k:
return []
if node.e <= maxRow and node.total >= k:
return [node.e, seats - node.total]
# we want to greedily search the left subtree to get the smallest row which has enough remain seats
if node.left.mx >= k:
return queryHelper(node.left)
return queryHelper(node.right)
return queryHelper(self.root)
def sumQuery(self, endRow):
def queryHelper(node, left, right):
if left <= node.s and node.e <= right:
return node.total
m = (node.s + node.e) // 2
if right <= m:
return queryHelper(node.left, left, right)
elif left > m:
return queryHelper(node.right, left, right)
return queryHelper(node.left, left, m) + queryHelper(node.right, m+1, right)
return queryHelper(self.root, 0, endRow)
class BookMyShow:
def __init__(self, n: int, m: int):
self.m = m
self.seg = SegTree(0, n-1, m)
# record the remain seats at each row
self.seats = [m] * n
# record the index of the smallest row that has remain seats > 0
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.sumQuery(maxRow) < k:
return False
else:
i = self.startRow
total = 0
while total < k:
prevTotal = total
total += self.seats[i]
if total < k:
# use up all the seats at ith row
self.seg.update(i, self.seats[i])
self.seats[i] = 0
i += 1
self.startRow = i
elif total >= k:
# occupy (k - prevTotal) seats at ith row
self.seg.update(i, k - prevTotal)
self.seats[i] -= k - prevTotal
return TrueBooking Concert Tickets in Groups LeetCode Solution in Java
class BookMyShow {
/**
Segment tree class to store sum of a range and maximum available seats in a row
**/
static class SegTree{
long sum[]; // store sum of seats in a range
long segTree[]; // store maximum seats in a range
int m, n;
public SegTree(int n, int m) {
this.m = m;
this.n = n;
segTree = new long[4*n];
sum = new long[4*n];
build(0, 0, n-1, m);
}
private void build(int index, int lo, int hi, long val){
if(lo == hi){
segTree[index] = val; // initialize segement tree with initial seat capacity
sum[index] = val; // initialize "sum" with initial seat capacity of a row
return;
}
int mid = (lo + hi)/2;
build(2*index +1, lo, mid, val); // build left sub tree
build(2*index +2, mid+1, hi, val); // build right sub tree
segTree[index] = Math.max(segTree[2*index + 1], segTree[2*index + 2]); // maximum seats in a row for subtrees
sum[index] = sum[2*index + 1] + sum[2*index + 2]; // sum of seats in a range
}
private void update(int index, int lo, int hi, int pos, int val){
/**
Method to update segment tree based on the available seats in a row
**/
if(lo == hi){
segTree[index] = val;
sum[index] = val;
return;
}
int mid = (lo + hi) / 2;
if (pos <= mid) { // position to update is in left
update(2 * index + 1, lo, mid, pos, val);
} else { // position to update is in right
update(2 * index + 2, mid+1, hi, pos, val);
}
// update segment tree and "sum" based on the update in "pos" index
segTree[index] = Math.max(segTree[2*index + 1] , segTree[2*index + 2]);
sum[index] = sum[2*index + 1] + sum[2*index + 2];
}
public void update(int pos, int val){
update(0, 0, n - 1 , pos, val);
}
public int gatherQuery(int k, int maxRow){
return gatherQuery(0, 0, n - 1 , k, maxRow);
}
private int gatherQuery(int index, int lo, int hi, int k, int maxRow){
/**
Method to check if seats are available in a single row
**/
if(segTree[index] < k || lo > maxRow)
return -1;
if(lo == hi) return lo;
int mid = (lo + hi) / 2;
int c = gatherQuery(2*index + 1, lo, mid, k, maxRow);
if(c == -1){
c = gatherQuery(2*index + 2, mid +1, hi, k, maxRow);
}
return c;
}
public long sumQuery(int k, int maxRow){
return sumQuery(0, 0, n-1, k, maxRow);
}
private long sumQuery(int index, int lo, int hi, int l, int r){
if(lo > r || hi < l ) return 0; // not in range
if(lo >= l && hi <= r) return sum[index]; // in range
int mid = (lo + hi)/2;
return sumQuery(2*index+1, lo, mid, l, r) + sumQuery(2*index+2, mid+1, hi, l, r);
}
}
SegTree segTree;
int[] rowSeats; // stores avaiable seats in a row, helps to find the vacant seat in a row
public BookMyShow(int n, int m) {
segTree = new SegTree(n, m);
rowSeats = new int[n];
Arrays.fill(rowSeats, m); // initialize vacant seats count to "m" for all the rows
}
public int[] gather(int k, int maxRow) {
int row = segTree.gatherQuery(k, maxRow); // find row which has k seats
if(row == -1) return new int[]{}; // can't find a row with k seats
int col = segTree.m - rowSeats[row]; // find column in the row which has k seats
rowSeats[row] -= k; // reduce the seats
segTree.update(row, rowSeats[row]); // update the segment tree
return new int[]{row, col};
}
public boolean scatter(int k, int maxRow) {
long sum = segTree.sumQuery(0, maxRow); // find the sum for the given range [0, maxRow]
if(sum < k) return false; // can't find k seats in [0, maxRow]
for(int i=0; i<=maxRow && k !=0 ; i++){
if(rowSeats[i] > 0){ // if current row has seats then allocate those seats
long t = Math.min(rowSeats[i], k);
rowSeats[i] -= t;
k -= t;
segTree.update(i,rowSeats[i]); // update the segment tree
}
}
return true;
}
}Booking Concert Tickets in Groups LeetCode Solution Review:
In our experience, we suggest you solve this Booking Concert Tickets in Groups LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Booking Concert Tickets in Groups LeetCode Solution
Conclusion:
I hope this Booking Concert Tickets in Groups LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More Coding Solutions >>
