Booking Concert Tickets in Groups - Practice Coding Problems

Booking Concert Tickets in Groups - Problem

Design a Concert Ticketing System

You're building a ticketing system for a popular concert venue! The concert hall has n rows (numbered 0 to n-1) with m seats each (numbered 0 to m-1).

Your system must handle two types of booking requests:

🎫 Group Seating (gather): A group of k people want to sit together in the same row
🎫 Flexible Seating (scatter): A group of k people are okay sitting apart, just want seats

The customers are picky though! They have these requirements:
• Only consider rows 0 through maxRow
• Always prefer the smallest row number available
• Within a row, prefer seats with smallest numbers

Your Task:
Implement BookMyShow class with:
• gather(k, maxRow): Returns [row, seat] of first seat for k consecutive seats, or [] if impossible
• scatter(k, maxRow): Returns true if k seats can be allocated (anywhere), false otherwise

Input & Output

example_1.py — Basic Operations

$ Input: ["BookMyShow", "gather", "gather", "scatter", "scatter"] [[2, 5], [4, 0], [2, 0], [5, 1], [5, 1]]

› Output: [null, [0, 0], [], true, false]

💡 Note: BookMyShow bms = new BookMyShow(2, 5); // 2 rows, 5 seats each bms.gather(4, 0); → [0, 0] (4 seats in row 0, starting at seat 0) bms.gather(2, 0); → [] (row 0 only has 1 seat left, can't fit 2 consecutive) bms.scatter(5, 1); → true (can scatter 5 people across rows 0-1) bms.scatter(5, 1); → false (not enough total seats remaining)

example_2.py — MaxRow Constraint

$ Input: ["BookMyShow", "gather", "gather", "gather"] [[3, 4], [2, 1], [3, 2], [2, 2]]

› Output: [null, [0, 0], [1, 0], [2, 0]]

💡 Note: BookMyShow bms = new BookMyShow(3, 4); // 3 rows, 4 seats each bms.gather(2, 1); → [0, 0] (row 0 available, fits 2 consecutive seats) bms.gather(3, 2); → [1, 0] (row 0 has only 2 seats left, use row 1) bms.gather(2, 2); → [2, 0] (rows 0,1 don't have enough consecutive seats)

example_3.py — Scatter vs Gather

$ Input: ["BookMyShow", "scatter", "gather", "scatter"] [[2, 3], [4, 1], [2, 1], [1, 1]]

› Output: [null, true, [], true]

💡 Note: BookMyShow bms = new BookMyShow(2, 3); // 2 rows, 3 seats each bms.scatter(4, 1); → true (scatter 4 people across rows 0-1: fills row 0 + 1 seat in row 1) bms.gather(2, 1); → [] (no row has 2 consecutive seats after scattering) bms.scatter(1, 1); → true (1 seat still available in row 1)

Constraints

1 ≤ n ≤ 5 × 10⁴
1 ≤ m, k ≤ 10⁹
0 ≤ maxRow ≤ n - 1
At most 5 × 10⁴ calls will be made to gather and scatter

Asked in

This problem requires efficient data structures to handle seat booking queries. The brute force approach scans each row linearly but is too slow for large inputs. The optimal solution uses segment trees to track maximum consecutive available seats per row and total available seats, enabling O(log n) queries instead of O(n*m). Key insight: maintain separate trees for consecutive seat queries (gather) and total seat counts (scatter).

Common Approaches

Approach	Time	Space	Notes
✓ Segment Tree with Binary Search	O(log n + log m)	O(n*m)	Use segment trees to efficiently query maximum consecutive seats and total available seats
Brute Force (Linear Scan)	O(n*m)	O(n*m)	Scan each row linearly to find available seats

Segment Tree with Binary Search — Algorithm Steps

Build segment tree for each row tracking max consecutive available seats
Build another segment tree tracking total available seats per row
For gather(): binary search to find first row with >= k consecutive seats
For scatter(): use prefix sum to check if total available seats >= k
Update both segment trees after booking seats

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Trees

Create segment trees for max consecutive and total available seats

Query Trees

Use log(n) queries to find suitable rows

Book Seats

Allocate seats in the optimal row

Update Trees

Propagate changes up the segment trees

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef struct {
    int n, m;
    int* availableFromLeft;
    int* maxConsecutive;
    long long* totalAvailable;
} BookMyShow;

void buildTrees(BookMyShow* obj, int node, int start, int end) {
    if (start == end) {
        obj->maxConsecutive[node] = obj->m;
        obj->totalAvailable[node] = obj->m;
    } else {
        int mid = (start + end) / 2;
        buildTrees(obj, 2 * node + 1, start, mid);
        buildTrees(obj, 2 * node + 2, mid + 1, end);
        obj->maxConsecutive[node] = 
            (obj->maxConsecutive[2 * node + 1] > obj->maxConsecutive[2 * node + 2]) ?
            obj->maxConsecutive[2 * node + 1] : obj->maxConsecutive[2 * node + 2];
        obj->totalAvailable[node] = 
            obj->totalAvailable[2 * node + 1] + obj->totalAvailable[2 * node + 2];
    }
}

long long queryTotalAvailable(BookMyShow* obj, int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return obj->totalAvailable[node];
    int mid = (start + end) / 2;
    return queryTotalAvailable(obj, 2 * node + 1, start, mid, l, r) +
           queryTotalAvailable(obj, 2 * node + 2, mid + 1, end, l, r);
}

void updateRow(BookMyShow* obj, int node, int start, int end, int idx, int consecutive, long long total) {
    if (start == end) {
        obj->maxConsecutive[node] = consecutive;
        obj->totalAvailable[node] = total;
    } else {
        int mid = (start + end) / 2;
        if (idx <= mid) {
            updateRow(obj, 2 * node + 1, start, mid, idx, consecutive, total);
        } else {
            updateRow(obj, 2 * node + 2, mid + 1, end, idx, consecutive, total);
        }
        obj->maxConsecutive[node] = 
            (obj->maxConsecutive[2 * node + 1] > obj->maxConsecutive[2 * node + 2]) ?
            obj->maxConsecutive[2 * node + 1] : obj->maxConsecutive[2 * node + 2];
        obj->totalAvailable[node] = 
            obj->totalAvailable[2 * node + 1] + obj->totalAvailable[2 * node + 2];
    }
}

BookMyShow* bookMyShowCreate(int n, int m) {
    BookMyShow* obj = (BookMyShow*)malloc(sizeof(BookMyShow));
    obj->n = n;
    obj->m = m;
    obj->availableFromLeft = (int*)malloc(n * sizeof(int));
    obj->maxConsecutive = (int*)malloc(4 * n * sizeof(int));
    obj->totalAvailable = (long long*)malloc(4 * n * sizeof(long long));
    
    for (int i = 0; i < n; i++) {
        obj->availableFromLeft[i] = m;
    }
    for (int i = 0; i < 4 * n; i++) {
        obj->maxConsecutive[i] = m;
        obj->totalAvailable[i] = m;
    }
    
    buildTrees(obj, 0, 0, n - 1);
    return obj;
}

int* bookMyShowGather(BookMyShow* obj, int k, int maxRow, int* returnSize) {
    maxRow = (maxRow < obj->n - 1) ? maxRow : obj->n - 1;
    
    for (int row = 0; row <= maxRow; row++) {
        if (obj->availableFromLeft[row] >= k) {
            int seat = obj->m - obj->availableFromLeft[row];
            obj->availableFromLeft[row] -= k;
            
            updateRow(obj, 0, 0, obj->n - 1, row, 
                     obj->availableFromLeft[row], 
                     obj->availableFromLeft[row]);
            
            int* result = (int*)malloc(2 * sizeof(int));
            result[0] = row;
            result[1] = seat;
            *returnSize = 2;
            return result;
        }
    }
    *returnSize = 0;
    return NULL;
}

bool bookMyShowScatter(BookMyShow* obj, int k, int maxRow) {
    maxRow = (maxRow < obj->n - 1) ? maxRow : obj->n - 1;
    long long totalAvail = queryTotalAvailable(obj, 0, 0, obj->n - 1, 0, maxRow);
    
    if (totalAvail < k) return false;
    
    int remaining = k;
    for (int row = 0; row <= maxRow && remaining > 0; row++) {
        int availableInRow = (remaining < obj->availableFromLeft[row]) ? 
                           remaining : obj->availableFromLeft[row];
        if (availableInRow > 0) {
            obj->availableFromLeft[row] -= availableInRow;
            remaining -= availableInRow;
            
            updateRow(obj, 0, 0, obj->n - 1, row,
                     obj->availableFromLeft[row],
                     obj->availableFromLeft[row]);
        }
    }
    
    return true;
}

void bookMyShowFree(BookMyShow* obj) {
    free(obj->availableFromLeft);
    free(obj->maxConsecutive);
    free(obj->totalAvailable);
    free(obj);
}

Time & Space Complexity

Time Complexity

⏱️

O(log n + log m)

Segment tree queries and updates are logarithmic

⚡ Linearithmic

Space Complexity

O(n*m)

Segment trees and seat tracking arrays

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen