2286. 分组预订音乐会门票

Hard

题目描述

一个音乐厅有 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 个组成员的第一个座位的行号和座位号。换句话说，它返回最小可能的 r 和 c，使得所有 [c, c + k - 1] 座位在第 r 行中都有效且空闲，且 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
                   // 大厅里只剩下一个座位了。

提示：

1 <= n <= 5 * 10^4
1 <= m, k <= 10^9
0 <= maxRow <= n - 1
总共最多对 gather 和 scatter 进行 5 * 10^4 次调用。

解题思路

这道题需要设计一个高效的座位预订系统。关键在于快速查询和更新区间信息。

核心思路：

数据结构选择：使用线段树维护两个信息：
- 每行的最大连续空座位数（用于 gather 操作）
- 每行的总空座位数（用于 scatter 操作）
gather 操作：
- 需要在 [0, maxRow] 范围内找到第一行，该行有至少 k 个连续空座位
- 使用线段树进行区间最大值查询，找到满足条件的最小行号
- 更新该行的座位信息
scatter 操作：
- 需要检查 [0, maxRow] 范围内总空座位数是否 >= k
- 使用线段树进行区间和查询
- 如果足够，则从第 0 行开始依次分配座位

实现要点：

线段树支持单点更新和区间查询（最大值查询用于 gather，求和查询用于 scatter）
维护每行当前的空座位起始位置，方便分配连续座位
gather 时需要精确更新行的连续空座位数
scatter 时按行号顺序贪心分配

推荐解法：线段树 + 贪心策略，时间复杂度为 O(log n)，空间复杂度为 O(n)。

代码实现

class BookMyShow {
private:
    int n, m;
    vector<long long> sum_tree, max_tree;
    vector<int> used;
    
    void update_sum(int v, int tl, int tr, int pos, long long val) {
        if (tl == tr) {
            sum_tree[v] = val;
        } else {
            int tm = (tl + tr) / 2;
            if (pos <= tm)
                update_sum(2*v, tl, tm, pos, val);
            else
                update_sum(2*v+1, tm+1, tr, pos, val);
            sum_tree[v] = sum_tree[2*v] + sum_tree[2*v+1];
        }
    }
    
    void update_max(int v, int tl, int tr, int pos, long long val) {
        if (tl == tr) {
            max_tree[v] = val;
        } else {
            int tm = (tl + tr) / 2;
            if (pos <= tm)
                update_max(2*v, tl, tm, pos, val);
            else
                update_max(2*v+1, tm+1, tr, pos, val);
            max_tree[v] = max(max_tree[2*v], max_tree[2*v+1]);
        }
    }
    
    long long query_sum(int v, int tl, int tr, int l, int r) {
        if (l > r) return 0;
        if (l == tl && r == tr) return sum_tree[v];
        int tm = (tl + tr) / 2;
        return query_sum(2*v, tl, tm, l, min(r, tm)) +
               query_sum(2*v+1, tm+1, tr, max(l, tm+1), r);
    }
    
    int query_max_row(int v, int tl, int tr, int l, int r, long long k) {
        if (l > r || max_tree[v] < k) return -1;
        if (tl == tr) return tl;
        int tm = (tl + tr) / 2;
        int left_res = query_max_row(2*v, tl, tm, l, min(r, tm), k);
        if (left_res != -1) return left_res;
        return query_max_row(2*v+1, tm+1, tr, max(l, tm+1), r, k);
    }
    
public:
    BookMyShow(int n, int m) : n(n), m(m) {
        sum_tree.resize(4 * n, m);
        max_tree.resize(4 * n, m);
        used.resize(n, 0);
    }
    
    vector<int> gather(int k, int maxRow) {
        int row = query_max_row(1, 0, n-1, 0, maxRow, k);
        if (row == -1) return {};
        
        int seat = used[row];
        used[row] += k;
        update_sum(1, 0, n-1, row, m - used[row]);
        update_max(1, 0, n-1, row, m - used[row]);
        
        return {row, seat};
    }
    
    bool scatter(int k, int maxRow) {
        if (query_sum(1, 0, n-1, 0, maxRow) < k) return false;
        
        for (int row = 0; row <= maxRow && k > 0; row++) {
            int available = m - used[row];
            int take = min(k, available);
            k -= take;
            used[row] += take;
            update_sum(1, 0, n-1, row, m - used[row]);
            update_max(1, 0, n-1, row, m - used[row]);
        }
        
        return true;
    }
};

class BookMyShow:
    def __init__(self, n: int, m: int):
        self.n = n
        self.m = m
        self.sum_tree = [m] * (4 * n)
        self.max_tree = [m] * (4 * n)
        self.used = [0] * n
    
    def update_sum(self, v, tl, tr, pos, val):
        if tl == tr:
            self.sum_tree[v] = val
        else:
            tm = (tl + tr) // 2
            if pos <= tm:
                self.update_sum(2*v, tl, tm, pos, val)
            else:
                self.update_sum(2*v+1, tm+1, tr, pos, val)
            self.sum_tree[v] = self.sum_tree[2*v] + self.sum_tree[2*v+1]
    
    def update_max(self, v, tl, tr, pos, val):
        if tl == tr:
            self.max_tree[v] = val
        else:
            tm = (tl + tr) // 2
            if pos <= tm:
                self.update_max(2*v, tl, tm, pos, val)
            else:
                self.update_max(2*v+1, tm+1, tr, pos, val)
            self.max_tree[v] = max(self.max_tree[2*v], self.max_tree[2*v+1])
    
    def query_sum(self, v, tl, tr, l, r):
        if l > r:
            return 0
        if l == tl and r == tr:
            return self.sum_tree[v]
        tm = (tl + tr) // 2
        return (self.query_sum(2*v, tl, tm, l, min(r, tm)) +
                self.query_sum(2*v+1, tm+1, tr, max(l, tm+1), r))
    
    def query_max_row(self, v, tl, tr, l, r, k):
        if l > r or self.max_tree[v] < k:
            return -1
        if tl == tr:
            return tl
        tm = (tl + tr) // 2
        left_res = self.query_max_row(2*v, tl, tm, l, min(r, tm), k)
        if left_res != -1:
            return left_res
        return self.query_max_row(2*v+1, tm+1, tr, max(l, tm+1), r, k)

    def gather(self, k: int, maxRow: int) -> List[int]:
        row = self.query_max_row(1, 0, self.n-1, 0, maxRow, k)
        if row == -1:
            return []
        
        seat = self.used[row]
        self.used[row] += k
        self.update_sum(1, 0, self.n-1, row, self.m - self.used[row])
        self.update_max(1, 0, self.n-1, row, self.m - self.used[row])
        
        return [row, seat]

    def scatter(self, k: int, maxRow: int) -> bool:
        if self.query_sum(1, 0, self.n-1, 0, maxRow) < k:
            return False
        
        for row in range(maxRow + 1):
            if k <= 0:
                break
            available = self.m - self.used[row]
            take = min(k, available)
            k -= take
            self.used[row] += take
            self.update_sum(1, 0, self.n-1, row, self.m - self.used[row])
            self.update_max(1, 0, self.n-1, row, self.m - self.used[row])
        
        return True

public class BookMyShow {
    private int n, m;
    private long[] sumTree, maxTree;
    private int[] used;
    
    public BookMyShow(int n, int m) {
        this.n = n;
        this.m = m;
        this.sumTree = new long[4 * n];
        this.maxTree = new long[4 * n];
        this.used = new int[n];
        
        Array.Fill(sumTree, m);
        Array.Fill(maxTree, m);
    }
    
    private void UpdateSum(int v, int tl, int tr, int pos, long val) {
        if (tl == tr) {
            sumTree[v] = val;
        } else {
            int tm = (tl + tr) / 2;
            if (pos <= tm)
                UpdateSum(2*v, tl, tm, pos, val);
            else
                UpdateSum(2*v+1, tm+1, tr, pos, val);
            sumTree[v] = sumTree[2*v] + sumTree[2*v+1];
        }
    }
    
    private void UpdateMax(int v, int tl, int tr, int pos, long val) {
        if (tl == tr) {
            maxTree[v] = val;
        } else {
            int tm = (tl + tr) / 2;
            if (pos <= tm)
                UpdateMax(2*v, tl, tm, pos, val);
            else
                UpdateMax(2*v+1, tm+1, tr, pos, val);
            maxTree[v] = Math.Max(maxTree[2*v], maxTree[2*v+1]);
        }
    }
    
    private long QuerySum(int v, int tl, int tr, int l, int r) {
        if (l > r) return 0;
        if (l == tl && r == tr) return sumTree[v];
        int tm = (tl + tr) / 2;
        return QuerySum(2*v, tl, tm, l, Math.Min(r, tm)) +
               QuerySum(2*v+1, tm+1, tr, Math.Max(l, tm+1), r);
    }
    
    private int QueryMaxRow(int v, int tl, int tr, int l, int r, long k) {
        if (l > r || maxTree[v] < k) return -1;
        if (tl == tr) return tl;
        int tm = (tl + tr) / 2;
        int leftRes = QueryMaxRow(2*v, tl, tm, l, Math.Min(r, tm), k);
        if (leftRes != -1) return leftRes;
        return QueryMaxRow(2*v+1, tm+1, tr, Math.Max(l, tm+1), r, k);
    }
    
    public int[] Gather(int k, int maxRow) {
        int row = QueryMaxRow(1, 0, n-1, 0, maxRow, k);
        if (row == -1) return new int[0];
        
        int seat = used[row];
        used[row] += k;
        UpdateSum(1, 0, n-1, row, m - used[row]);
        UpdateMax(1, 0, n-1, row, m - used[row]);
        
        return new int[] {row, seat};
    }
    
    public bool Scatter(int k, int maxRow) {
        if (QuerySum(1, 0, n-1, 0, maxRow) < k) return false;
        
        for (int row = 0; row <= maxRow && k > 0; row++) {
            int available = m - used[row];
            int take = Math.Min(k, available);
            k -= take;
            used[row] += take;
            UpdateSum(1, 0, n-1, row, m - used[row]);
            UpdateMax(1, 0, n-1, row, m - used[row]);
        }
        
        return true;
    }
}

var BookMyShow = function(n, m) {
    this.n = n;
    this.m = m;
    this.rows = new Array(n).fill(0);
    this.maxTree = new Array(4 * n).fill(0);
    this.sumTree = new Array(4 * n).fill(0);
    this.buildMax(1, 0, n - 1);
    this.buildSum(1, 0, n - 1);
};

BookMyShow.prototype.buildMax = function(node, start, end) {
    if (start === end) {
        this.maxTree[node] = this.m;
    } else {
        let mid = Math.floor((start + end) / 2);
        this.buildMax(2 * node, start, mid);
        this.buildMax(2 * node + 1, mid + 1, end);
        this.maxTree[node] = Math.max(this.maxTree[2 * node], this.maxTree[2 * node + 1]);
    }
};

BookMyShow.prototype.buildSum = function(node, start, end) {
    if (start === end) {
        this.sumTree[node] = this.m;
    } else {
        let mid = Math.floor((start + end) / 2);
        this.buildSum(2 * node, start, mid);
        this.buildSum(2 * node + 1, mid + 1, end);
        this.sumTree[node] = this.sumTree[2 * node] + this.sumTree[2 * node + 1];
    }
};

BookMyShow.prototype.queryMax = function(node, start, end, l, r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return this.maxTree[node];
    let mid = Math.floor((start + end) / 2);
    return Math.max(this.queryMax(2 * node, start, mid, l, r),
                   this.queryMax(2 * node + 1, mid + 1, end, l, r));
};

BookMyShow.prototype.querySum = function(node, start, end, l, r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return this.sumTree[node];
    let mid = Math.floor((start + end) / 2);
    return this.querySum(2 * node, start, mid, l, r) +
           this.querySum(2 * node + 1, mid + 1, end, l, r);
};

BookMyShow.prototype.findFirstMax = function(node, start, end, l, r, val) {
    if (r < start || end < l || this.maxTree[node] < val) return -1;
    if (start === end) return start;
    let mid = Math.floor((start + end) / 2);
    let left = this.findFirstMax(2 * node, start, mid, l, r, val);
    if (left !== -1) return left;
    return this.findFirstMax(2 * node + 1, mid + 1, end, l, r, val);
};

BookMyShow.prototype.update = function(node, start, end, idx, val) {
    if (start === end) {
        this.maxTree[node] = val;
        this.sumTree[node] = val;
    } else {
        let mid = Math.floor((start + end) / 2);
        if (idx <= mid) {
            this.update(2 * node, start, mid, idx, val);
        } else {
            this.update(2 * node + 1, mid + 1, end, idx, val);
        }
        this.maxTree[node] = Math.max(this.maxTree[2 * node], this.maxTree[2 * node + 1]);
        this.sumTree[node] = this.sumTree[2 * node] + this.sumTree[2 * node + 1];
    }
};

BookMyShow.prototype.gather = function(k, maxRow) {
    let row = this.findFirstMax(1, 0, this.n - 1, 0, maxRow, k);
    if (row === -1) return [];
    
    let seat = this.m - this.rows[row];
    this.rows[row] += k;
    this.update(1, 0, this.n - 1, row, this.m - this.rows[row]);
    
    return [row, seat];
};

BookMyShow.prototype.scatter = function(k, maxRow) {
    let totalAvailable = this.querySum(1, 0, this.n - 1, 0, maxRow);
    if (totalAvailable < k) return false;
    
    for (let i = 0; i <= maxRow && k > 0; i++) {
        let available = this.m - this.rows[i];
        let take = Math.min(available, k);
        this.rows[i] += take;
        k -= take;
        this.update(1, 0, this.n - 1, i, this.m - this.rows[i]);
    }
    
    return true;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
构造函数	O(n)	O(n)
gather	O(log n)	O(1)
scatter	O(min(k/m, maxRow) + log n)	O(1)

解释：

构造函数需要初始化线段树和辅助数组，时间和空间复杂度均为 O(n)
gather 操作需要进行线段树的区间最大值查询和单点更新，时间复杂度为 O(log n)
scatter 操作在最坏情况下需要遍历所有可用行，但由于每次调用最多分配 k 个座位，实际复杂度受限于座位数量，加上线段树更新操作，总体复杂度为 O(min(k/m, maxRow) + log n)
两个操作的额外空间复杂度均为 O(1)

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目