LeetCode 2286: Booking Concert Tickets in Groups Solution
Master LeetCode problem 2286 (Booking Concert Tickets in Groups), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
2286. Booking Concert Tickets in Groups
Problem Explanation
Explanation:
To solve this problem, we can maintain a data structure to keep track of the available seats in each row. When a group wants to gather together, we can check row by row for the first available consecutive seats that satisfy the constraints. When a group wants to scatter, we can check row by row for the first available non-consecutive seats that satisfy the constraints.
Algorithm:
- Initialize a data structure to track available seats in each row.
- For the gather method:
- Iterate over each row and find the first row with k consecutive available seats within the maxRow limit.
- If found, mark those seats as occupied and return the row and seat number.
- If no such seats are available, return an empty array.
- For the scatter method:
- Iterate over each row and find the first row with k available seats within the maxRow limit.
- If found, mark those seats as occupied and return true.
- If no such seats are available, return false.
Time Complexity:
- For the gather method, the time complexity is O(n*m) where n is the number of rows and m is the number of seats per row.
- For the scatter method, the time complexity is also O(n*m).
Space Complexity:
The space complexity is O(n*m) to store the status of each seat in the concert hall.
:
Solution Code
class BookMyShow {
int rows, seats;
boolean[][] hall;
public BookMyShow(int n, int m) {
rows = n;
seats = m;
hall = new boolean[n][m];
}
public int[] gather(int k, int maxRow) {
for (int i = 0; i <= maxRow; i++) {
int count = 0;
int startSeat = -1;
for (int j = 0; j < seats; j++) {
if (!hall[i][j]) {
if (startSeat == -1) {
startSeat = j;
}
count++;
} else {
startSeat = -1;
count = 0;
}
if (count == k) {
for (int x = startSeat; x < startSeat + k; x++) {
hall[i][x] = true;
}
return new int[]{i, startSeat};
}
}
}
return new int[]{};
}
public boolean scatter(int k, int maxRow) {
for (int i = 0; i <= maxRow; i++) {
int count = 0;
for (int j = 0; j < seats; j++) {
if (!hall[i][j]) {
count++;
if (count == k) {
for (int x = j - k + 1; x <= j; x++) {
hall[i][x] = true;
}
return true;
}
} else {
count = 0;
}
}
}
return false;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 2286 (Booking Concert Tickets in Groups)?
This page provides optimized solutions for LeetCode problem 2286 (Booking Concert Tickets in Groups) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 2286 (Booking Concert Tickets in Groups)?
The time complexity for LeetCode 2286 (Booking Concert Tickets in Groups) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 2286 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2286 in Java, C++, or Python.