2286. Booking Concert Tickets in Groups LeetCode Solution
In this guide, you will get 2286. Booking Concert Tickets in Groups LeetCode Solution with the best time and space complexity. The solution to Booking Concert Tickets in Groups problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Booking Concert Tickets in Groups
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 maxRow. maxRow 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.
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.
Complexity Analysis
Time Complexity: O(k)
Space Complexity: O(n)
2286. Booking Concert Tickets in Groups LeetCode Solution in C++
struct SegmentTreeNode {
int lo;
int hi;
std::unique_ptr<SegmentTreeNode> left;
std::unique_ptr<SegmentTreeNode> right;
int mx;
long sum;
SegmentTreeNode(int lo, int hi, std::unique_ptr<SegmentTreeNode>&& left,
std::unique_ptr<SegmentTreeNode>&& right, int mx, long sum)
: lo(lo),
hi(hi),
left(std::move(left)),
right(std::move(right)),
mx(mx),
sum(sum) {}
};
class SegmentTree {
public:
explicit SegmentTree(int n, int m) : m(m), root(std::move(build(0, n - 1))) {}
vector<int> maxRange(int k, int maxRow) {
return maxRange(root, k, maxRow);
}
long sumRange(int maxRow) {
return sumRange(root, 0, maxRow);
}
// Substracts k from the seats row.
void substract(int row, int k) {
substract(root, row, k);
}
private:
const int m;
std::unique_ptr<SegmentTreeNode> root;
std::unique_ptr<SegmentTreeNode> build(int l, int r) {
if (l == r)
return make_unique<SegmentTreeNode>(l, r, nullptr, nullptr, m, m);
const int mid = (l + r) / 2;
std::unique_ptr<SegmentTreeNode> left = build(l, mid);
std::unique_ptr<SegmentTreeNode> right = build(mid + 1, r);
return make_unique<SegmentTreeNode>(l, r, std::move(left), std::move(right),
max(left->mx, right->mx),
left->sum + right->sum);
}
vector<int> maxRange(std::unique_ptr<SegmentTreeNode>& root, int k,
int maxRow) {
if (root->lo == root->hi) {
if (root->sum < k || root->lo > maxRow)
return {};
return {root->lo, m - static_cast<int>(root->sum)}; // {row, col}
}
// Greedily search the left subtree
if (root->left->mx >= k)
return maxRange(root->left, k, maxRow);
return maxRange(root->right, k, maxRow);
}
long sumRange(std::unique_ptr<SegmentTreeNode>& root, int i, int j) {
if (root->lo == i && root->hi == j)
return root->sum;
const int mid = (root->lo + root->hi) / 2;
if (j <= mid)
return sumRange(root->left, i, j);
if (i > mid)
return sumRange(root->right, i, j);
return sumRange(root->left, i, mid) + sumRange(root->right, mid + 1, j);
}
void substract(std::unique_ptr<SegmentTreeNode>& root, int row, int k) {
if (root == nullptr)
return;
if (root->lo == root->hi && root->hi == row) {
root->mx -= k;
root->sum -= k;
return;
}
const int mid = (root->lo + root->hi) / 2;
if (row <= mid)
substract(root->left, row, k);
else
substract(root->right, row, k);
root->mx = max(root->left->mx, root->right->mx);
root->sum = root->left->sum + root->right->sum;
}
};
class BookMyShow {
public:
BookMyShow(int n, int m) : tree(n, m), seats(n, m) {}
vector<int> gather(int k, int maxRow) {
const vector<int> res = tree.maxRange(k, maxRow);
if (res.size() == 2) {
const int row = res[0];
tree.substract(row, k);
seats[row] -= k;
}
return res;
}
bool scatter(int k, int maxRow) {
if (tree.sumRange(maxRow) < k)
return false;
while (k > 0)
if (seats[minVacantRow] >= k) {
tree.substract(minVacantRow, k);
seats[minVacantRow] -= k;
k = 0;
} else {
tree.substract(minVacantRow, seats[minVacantRow]);
k -= seats[minVacantRow];
seats[minVacantRow] = 0;
++minVacantRow;
}
return true;
}
private:
SegmentTree tree;
vector<int> seats; // the remaining seats at each row
int minVacantRow = 0;
}; /* code provided by PROGIEZ */
2286. Booking Concert Tickets in Groups LeetCode Solution in Java
N/A // code provided by PROGIEZ
2286. Booking Concert Tickets in Groups LeetCode Solution in Python
