Skip to main content

Booking Concert Tickets in Groups

Problem​

A concert hall has nn rows numbered from 00 to n−1n - 1, each with mm seats, numbered from 00 to m−1m - 1. You need to design a ticketing system that can allocate seats in the following cases:

  • If a group of kk spectators can sit together in a row.
  • If every member of a group of kk 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. 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 BookMyShowBookMyShow class:

  • BookMyShow(intn,intm)BookMyShow(int n, int m) Initializes the object with nn as number of rows and mm as number of seats per row.

  • int[]gather(intk,intmaxRow)int[] gather(int k, int maxRow) Returns an array of length 22 denoting the row and seat number (respectively) of the first seat being allocated to the kk members of the group, who must sit together. In other words, it returns the smallest possible rr and cc such that all [c,c+k−1][c, c + k - 1] seats are valid and empty in row rr, and r<=maxRowr <= maxRow. Returns [][] in case it is not possible to allocate seats to the group.

  • booleanscatter(intk,intmaxRow)boolean scatter(int k, int maxRow) Returns truetrue if all kk members of the group can be allocated seats in rows 00 to maxRowmaxRow, who may or may not sit together. If the seats can be allocated, it allocates kk seats to the group with the smallest row numbers, and the smallest possible seat numbers in each row. Otherwise, returns falsefalse.

Examples​

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 <= n <= 5 * 10^4
  • 1<=m,k<=1091 <= m, k <= 10^9
  • 0<=maxRow<=n−10 <= maxRow <= n - 1
  • At most 5∗1045 * 10^4 calls in total will be made to gathergather and scatterscatter.

Approach​

To solve the problem, we need to understand the nature of the allowed moves:

  1. Segment Tree:

    • Build: Construct the segment tree with initial values, where each node stores the sum and maximum number of seats in the range it represents.

    • Update: Update the segment tree when seats are booked, modifying the relevant nodes to reflect the new seat counts.

    • Queries:

      • Gather Query: Find a row with at least 'k' seats available within the first 'maxRow' rows.

      • Sum Query: Compute the total number of seats available within the first 'maxRow' rows.

  2. BookMyShow Class:

    • Constructor: Initialize the segment tree and an array to keep track of seats available in each row.
    • Gather: Check if there is a row with at least 'k' seats and update the tree and row seat count accordingly.
    • Scatter: Allocate 'k'

Solution for Booking Concert Tickets in Groups​

  • The problem revolves around efficiently managing and querying seat allocations in a theater. The segment tree is used to handle range queries and updates swiftly, ensuring that operations like finding available seats or updating seat counts are performed in logarithmic time.

Code in Java​

class BookMyShow {
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;
}
}

Complexity Analysis​

Time Complexity: O(logn)O(logn)​

Reason: Segment tree operations are build: O(n)O(n), update: O(logn)O(log n), gather query: O(logn)O(log n), sum query: O(logn)O(log n); BookMyShow operations are constructor: O(n)O(n), gather: O(logn)O(log n), scatter: O(nlogn)O(n log n).

Space Complexity: O(n)O(n)​

Reason: The space complexity is O(n)O(n), The 'rowSeats' array requires O(n) space to store the seat counts for each row.

References