Booking concert tickets in groups

Binary Search Design Binary Indexed Tree Segment Tree

19.2% acceptance

Feb 23, 2026

351

A school is trying to take an annual photo of all the students. The students are asked to stand in a single file line in non-decreasing order by height. Let this ordering be represented by the integer array expected where expected[i] is the expected height of the ith student in line. You are given an integer array heights representing the current order that the students are standing in. Each heights[i] is the height of the ith student in line (0-indexed). Return the number of indices where heights[i] != expected[i]. Wait, this is actually problem 2286 - Book My Show Implement a system that manages the booking of n rows and m seats per row for a concert. - BookMyShow(int n, int m) Initializes the object with n rows of m seats each. - int[] gather(int k, int maxRow) Returns an array of length 2 denoting the row and the first seat, or returns [] if it is not possible to allocate k consecutive seats in the same row such that the row number is at most maxRow. - boolean scatter(int k, int maxRow) Returns true if it is possible to allocate k seats in consecutive rows such that the row number is at most maxRow, otherwise returns false. In this process, fill the seats in as few rows as possible.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

pub struct BookMyShow {
  n: usize,
  m: i64,
  max_t: Vec<i64>,
  sum_t: Vec<i64>,
}

impl BookMyShow {
  pub fn new(n: i32, m: i32) -> Self {
    let n = n as usize;
    let m = m as i64;
    let sz = 4 * (n + 1);
    let mut bms = BookMyShow { n, m, max_t: vec![0; sz], sum_t: vec![0; sz] };
    bms.build(1, 0, n - 1);
    bms
  }

  fn build(&mut self, v: usize, l: usize, r: usize) {
    self.max_t[v] = self.m;
    if l == r {
      self.sum_t[v] = self.m;
      return;
    }
    let mid = (l + r) / 2;
    self.build(2 * v, l, mid);
    self.build(2 * v + 1, mid + 1, r);
    self.sum_t[v] = self.sum_t[2 * v] + self.sum_t[2 * v + 1];
  }

  fn update(&mut self, v: usize, l: usize, r: usize, pos: usize, val: i64) {
    if l == r {
      self.sum_t[v] = val;
      self.max_t[v] = val;
      return;
    }
    let mid = (l + r) / 2;
    if pos <= mid {
      self.update(2 * v, l, mid, pos, val);
    } else {
      self.update(2 * v + 1, mid + 1, r, pos, val);
    }
    self.sum_t[v] = self.sum_t[2 * v] + self.sum_t[2 * v + 1];
    self.max_t[v] = self.max_t[2 * v].max(self.max_t[2 * v + 1]);
  }

  fn query_sum(&self, v: usize, l: usize, r: usize, ql: usize, qr: usize) -> i64 {
    if r < ql || l > qr {
      return 0;
    }
    if ql <= l && r <= qr {
      return self.sum_t[v];
    }
    let mid = (l + r) / 2;
    self.query_sum(2 * v, l, mid, ql, qr) + self.query_sum(2 * v + 1, mid + 1, r, ql, qr)
  }

  fn find_first(&self, v: usize, l: usize, r: usize, ql: usize, qr: usize, k: i64) -> i32 {
    if r < ql || l > qr || self.max_t[v] < k {
      return -1;
    }
    if l == r {
      return l as i32;
    }
    let mid = (l + r) / 2;
    let left = self.find_first(2 * v, l, mid, ql, qr, k);
    if left != -1 {
      return left;
    }
    self.find_first(2 * v + 1, mid + 1, r, ql, qr, k)
  }

  fn scatter_fill(&mut self, v: usize, l: usize, r: usize, ql: usize, qr: usize, k: &mut i64) {
    if *k <= 0 || r < ql || l > qr || self.sum_t[v] == 0 {
      return;
    }
    if l == r {
      let take = (*k).min(self.sum_t[v]);
      *k -= take;
      let nv = self.sum_t[v] - take;
      self.sum_t[v] = nv;
      self.max_t[v] = nv;
      return;
    }
    let mid = (l + r) / 2;
    self.scatter_fill(2 * v, l, mid, ql, qr, k);
    self.scatter_fill(2 * v + 1, mid + 1, r, ql, qr, k);
    self.sum_t[v] = self.sum_t[2 * v] + self.sum_t[2 * v + 1];
    self.max_t[v] = self.max_t[2 * v].max(self.max_t[2 * v + 1]);
  }

  pub fn gather(&mut self, k: i32, max_row: i32) -> Vec<i32> {
    let k = k as i64;
    let max_row = max_row as usize;
    let n = self.n;
    let row = self.find_first(1, 0, n - 1, 0, max_row, k);
    if row == -1 {
      return vec![];
    }
    let row = row as usize;
    let avail = self.query_sum(1, 0, n - 1, row, row);
    let first_seat = self.m - avail;
    self.update(1, 0, n - 1, row, avail - k);
    vec![row as i32, first_seat as i32]
  }

  pub fn scatter(&mut self, k: i32, max_row: i32) -> bool {
    let k = k as i64;
    let max_row = max_row as usize;
    let n = self.n;
    let total = self.query_sum(1, 0, n - 1, 0, max_row);
    if total < k {
      return false;
    }
    let mut remaining = k;
    self.scatter_fill(1, 0, n - 1, 0, max_row, &mut remaining);
    true
  }
}