题目：
一个音乐会总共有 n 排座位，编号从 0 到 n - 1 ，每一排有 m 个座椅，编号为 0 到 m - 1 。你需要设计一个买票系统，针对以下情况进行座位安排：
- 同一组的
k位观众坐在 同一排座位，且座位连续 。 k位观众中 每一位 都有座位坐，但他们 不一定 坐在一起。
由于观众非常挑剔，所以：
- 只有当一个组里所有成员座位的排数都 小于等于
maxRow，这个组才能订座位。每一组的maxRow可能 不同 。 - 如果有多排座位可以选择，优先选择 最小 的排数。如果同一排中有多个座位可以坐，优先选择号码 最小 的。
请你实现 BookMyShow 类：
BookMyShow(int n, int m)，初始化对象，n是排数，m是每一排的座位数。int[] gather(int k, int maxRow)返回长度为2的数组，表示k个成员中 第一个座位 的排数和座位编号，这k位成员必须坐在 同一排座位，且座位连续 。换言之，返回最小可能的r和c满足第r排中[c, c + k - 1]的座位都是空的，且r <= maxRow。如果 无法 安排座位，返回[]。boolean scatter(int k, int maxRow)如果组里所有k个成员 不一定 要坐在一起的前提下，都能在第0排到第maxRow排之间找到座位，那么请返回true。这种情况下，每个成员都优先找排数 最小 ，然后是座位编号最小的座位。如果不能安排所有k个成员的座位，请返回false。
示例 1：
输入：
["BookMyShow", "gather", "gather", "scatter", "scatter"]
[[2, 5], [4, 0], [2, 0], [5, 1], [5, 1]]
输出：
[null, [0, 0], [], true, false]
解释：
BookMyShow bms = new BookMyShow(2, 5); // 总共有 2 排，每排 5 个座位。
bms.gather(4, 0); // 返回 [0, 0]
// 这一组安排第 0 排 [0, 3] 的座位。
bms.gather(2, 0); // 返回 []
// 第 0 排只剩下 1 个座位。
// 所以无法安排 2 个连续座位。
bms.scatter(5, 1); // 返回 True
// 这一组安排第 0 排第 4 个座位和第 1 排 [0, 3] 的座位。
bms.scatter(5, 1); // 返回 False
// 总共只剩下 2 个座位。
提示：
1 <= n <= 5 * 1041 <= m, k <= 1090 <= maxRow <= n - 1gather和scatter总 调用次数不超过5 * 104次。
模拟
思路：
由于客户都偏向于落座低排，低索引，所以通过维护每一排可以做人的最小索引，进而对每一组客户落座进行模拟。
代码：
class BookMyShow {
public:
//vector<vector<bool>> seat;
vector<int> minIdx;
int n;
int m;
BookMyShow(int n, int m) {
//seat.resize(n, vector<bool>(m, false));
minIdx.resize(n, 0);
this->n = n;
this->m = m;
}
vector<int> gather(int k, int maxRow) {
vector<int> ans;
if (k > m) return ans;
for (int i = 0; i <= maxRow; i++) {
if (m - minIdx[i] >= k) {
ans.push_back(i);
ans.push_back(minIdx[i]);
minIdx[i] += k;
return ans;
}
}
return ans;
}
bool scatter(int k, int maxRow) {
vector<int> temp = minIdx;
bool flag = false;
for (int i = 0; i <= maxRow; i++) {
if (temp[i] < m) {
if (m - temp[i] >= k) {
// 这一排就可以直接完成所有人坐满
temp[i] += k;
flag = true;
break;
} else {
k -= (m - temp[i]);
temp[i] = m;
}
}
}
if (flag) minIdx = temp;
return flag;
}
};
/**
* Your BookMyShow object will be instantiated and called as such:
* BookMyShow* obj = new BookMyShow(n, m);
* vector<int> param_1 = obj->gather(k,maxRow);
* bool param_2 = obj->scatter(k,maxRow);
*/
线段树
思路：
我们使用两个线段树 minTree 和 sumTree 分别维护区间 [l, r]，即第 l 排到第 r 排座位内：
最小已坐座位数
已坐座位数之和
对于两种座位安排 gather 和 scatter，我们分开讨论：
gather 函数
根据题意，我们只需要找到区间 [0, maxRow] 内，已坐座位数 used ≤ m − k，且排数最小的那一排座位，然后返回安排的座位。
我们可以在 minTree 上进行二分搜索，从区间 [0, n − 1] 开始搜索，如果前半区间的最小已坐座位数 used 小于等于 m − k，那么继续搜索前半区间，否则搜索后半区间。令搜索到的座位排数为 i，对应的已坐座位数为 usedi ，如果 i > maxRow，那么说明无法安排座位，否则返回 i, usedi 为结果，同时修改第 i 排已坐座位数为 usedi + k。
scatter 函数
根据题意，我们首先需要获取区间 [0, maxRow] 内的所有剩余座位之和，如果小于 k，那么说明无法安排座位；否则，我们从第一排未坐满的排开始选择，直到座位全部安排完成。
通过 sumTree 可以获取区间 [0, maxRow] 内的所有已坐座位之和 usedTotal，那么剩余座位之和为 (maxRow + 1) * m − usedTotal。通过 minTree 可以二分搜索已坐座位数小于等于 m − 1 的最小座位排数，即第一排未坐满的排。然后按照上述步骤安排座位。
代码：
class BookMyShow {
private:
int n;
int m;
vector<int> minTree;
vector<long long> sumTree;
void modify(int i, int l, int r, int index, int val) {
if (l == r) {
minTree[i] = val;
sumTree[i] = val;
return;
}
int mid = (l + r) / 2;
if (index <= mid) {
modify(i * 2, l, mid, index, val);
} else {
modify(i * 2 + 1, mid + 1, r, index, val);
}
minTree[i] = min(minTree[i * 2], minTree[i * 2 + 1]);
sumTree[i] = sumTree[i * 2] + sumTree[i * 2 + 1];
}
int queryMinRow(int i, int l, int r, int val) {
if (l == r) {
if (minTree[i] > val) {
return n;
}
return l;
}
int mid = (l + r) / 2;
if (minTree[i * 2] <= val) {
return queryMinRow(i * 2, l, mid, val);
} else {
return queryMinRow(i * 2 + 1, mid + 1, r, val);
}
}
long long querySum(int i, int l, int r, int l2, int r2) {
if (l2 <= l && r <= r2) {
return sumTree[i];
}
int mid = (l + r) / 2;
long long sum = 0;
if (mid >= l2) {
sum += querySum(i * 2, l, mid, l2, r2);
}
if (mid + 1 <= r2) {
sum += querySum(i * 2 + 1, mid + 1, r, l2, r2);
}
return sum;
}
public:
BookMyShow(int n, int m): n(n), m(m), minTree(4 * n), sumTree(4 * n) {
}
vector<int> gather(int k, int maxRow) {
int i = queryMinRow(1, 0, n - 1, m - k);
if (i > maxRow) {
return {};
}
int used = querySum(1, 0, n - 1, i, i);
modify(1, 0, n - 1, i, used + k);
return {i, used};
}
bool scatter(int k, int maxRow) {
long long usedTotal = querySum(1, 0, n - 1, 0, maxRow);
if ((long long)(maxRow + 1) * m - usedTotal < k) {
return false;
}
int i = queryMinRow(1, 0, n - 1, m - 1);
while (true) {
long long used = querySum(1, 0, n - 1, i, i);
if (m - used >= k) {
modify(1, 0, n - 1, i, used + k);
break;
}
k -= m - used;
modify(1, 0, n - 1, i, m);
i++;
}
return true;
}
};