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

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 True

Booking 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

Find on LeetCode

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

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.