2286-以组为单位订音乐会的门票

一个音乐会总共有 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 * 104
• 1 <= m, k <= 109
• 0 <= maxRow <= n - 1
• gather 和 scatter 总 调用次数不超过 5 * 104 次。

解法

思路和算法

这道题要求对于 n 排 m 列的音乐厅设计一个音乐会买票系统，支持两种买票方式。

• 同一组的 k 位观众在同一排坐在一起。该方式对应 gather，称为聚集买票。

• 同一组的 k 位观众不一定坐在一起。该方式对应 scatter，称为分散买票。

由于两种买票方式都应满足对于特定排选择编号最小的座位，因此任何时候总是满足每一排订的座位是这一排的编号最小的连续座位。如果有一排已经订了 s 个座位，其中 0 < s \le m，则一定满足这一排的编号 0 到 s - 1 的座位被订座，编号 s 到 m - 1 的座位没有被订座。因此对于每一排，被订座的座位数量与座位编号可以互相换算。

两种买票方式的要求分别如下。

• 聚集买票要求在排数不超过 maxRow 的范围判断是否存在有 k 个空座位的排，如果存在则需要计算排数最小的排的编号和这一排第一个空座位的编号，完成买票。

• 分散买票要求在排数不超过 maxRow 的范围判断是否有至少 k 个空座位的票，如果存在则需要计算买票的所有座位，完成买票。

为了实现两种买票方式，需要维护每一排的第一个空座位的编号与空座位数量，并需要支持快速计算特定排数范围的空座位的数量与第一个空座位的编号。可以使用线段树实现，线段树需要维护每个区间的被订座的座位数量与第一个空座位的编号。

聚集买票的做法如下。

1. 如果一排可以买 k 个连续座位的票，则这一排的编号 m - k 到 m - 1 的座位一定都是空座位，因此这一排第一个空座位的编号不超过 m - k。计算排数不超过 maxRow 的范围的第一个空座位的编号不超过 m - k 的最小排数 row，如果排数不超过 maxRow 的范围的每一排的第一个空座位的编号都超过 m - k 则 row} = -1。将一个区间分成两个子区间之后，由于原始区间的第一个空座位编号的最小值等于两个子区间的第一个空座位编号的最小值中的最小值，因此可以使用二分查找计算最小排数。

2. 如果 row} < 0，则排数不超过 maxRow 的范围不存在第一个空座位的编号不超过 m - k 的排，返回空数组。

3. 如果 row} \ge 0，则 row 是第一个空座位的编号不超过 m - k 的最小排数。计算第 row 排的被订座的座位数量 seats，则第 row 排的第一个空座位的编号是 seats。将第 row 排的被订座的座位数量增加 k，然后返回 [\textit{row}, \textit{seats}]。

分散买票的做法如下。

1. 排数不超过 maxRow 的范围的座位总数是 (\textit{maxRow} + 1) \times m。计算排数不超过 maxRow 的范围的被订座的座位数量，根据座位总数与被订座的座位数量之差得到排数不超过 maxRow 的范围的空座位数量 remain。

2. 如果 remain} < k，则空座位数量小于 k，不能安排座位，返回 false。

3. 如果 remain} \ge k，则空座位数量大于等于 k，可以安排座位。定位到有空座位的最小排数 row，从第 row 排开始依次计算每一排的空座位数量并完成订座，直到安排 k 个座位时订座结束。订座结束之后，返回 true。

代码

[sol1-Java]

class BookMyShow {
    private int n, m;
    private SegmentTree st;

    public BookMyShow(int n, int m) {
        this.n = n;
        this.m = m;
        this.st = new SegmentTree(n);
    }

    public int[] gather(int k, int maxRow) {
        int row = st.searchRow(m - k, maxRow);
        if (row < 0) {
            return new int[0];
        }
        int seats = (int) st.getSum(row, row);
        st.add(row, k);
        return new int[]{row, seats};
    }

    public boolean scatter(int k, int maxRow) {
        long remain = (long) (maxRow + 1) * m - st.getSum(0, maxRow);
        if (remain < k) {
            return false;
        }
        int row = st.searchRow(m - 1, maxRow);
        while (k > 0) {
            int currRemain = m - (int) st.getSum(row, row);
            int currSeats = Math.min(currRemain, k);
            st.add(row, currSeats);
            k -= currSeats;
            row++;
        }
        return true;
    }
}

class SegmentTree {
    private int n;
    private long[] sumTree;
    private int[] minTree;

    public SegmentTree(int n) {
        this.n = n;
        this.sumTree = new long[n * 4];
        this.minTree = new int[n * 4];
    }

    public long getSum(int start, int end) {
        return getSum(start, end, 0, 0, n - 1);
    }

    public void add(int index, int value) {
        add(index, value, 0, 0, n - 1);
    }

    public int searchRow(int target, int maxRow) {
        return searchRow(target, maxRow, 0, 0, n - 1);
    }

    private long getSum(int rangeStart, int rangeEnd, int treeIndex, int treeStart, int treeEnd) {
        if (rangeStart == treeStart && rangeEnd == treeEnd) {
            return sumTree[treeIndex];
        }
        int mid = treeStart + (treeEnd - treeStart) / 2;
        if (rangeEnd <= mid) {
            return getSum(rangeStart, rangeEnd, treeIndex * 2 + 1, treeStart, mid);
        } else if (rangeStart > mid) {
            return getSum(rangeStart, rangeEnd, treeIndex * 2 + 2, mid + 1, treeEnd);
        } else {
            return getSum(rangeStart, mid, treeIndex * 2 + 1, treeStart, mid) + getSum(mid + 1, rangeEnd, treeIndex * 2 + 2, mid + 1, treeEnd);
        }
    }

    private void add(int rangeIndex, int value, int treeIndex, int start, int end) {
        if (start == end) {
            sumTree[treeIndex] += value;
            minTree[treeIndex] += value;
            return;
        }
        int mid = start + (end - start) / 2;
        if (rangeIndex <= mid) {
            add(rangeIndex, value, treeIndex * 2 + 1, start, mid);
        } else {
            add(rangeIndex, value, treeIndex * 2 + 2, mid + 1, end);
        }
        sumTree[treeIndex] = sumTree[treeIndex * 2 + 1] + sumTree[treeIndex * 2 + 2];
        minTree[treeIndex] = Math.min(minTree[treeIndex * 2 + 1], minTree[treeIndex * 2 + 2]);
    }

    private int searchRow(int target, int maxRow, int treeIndex, int start, int end) {
        if (minTree[treeIndex] > target) {
            return -1;
        }
        if (start == end) {
            return start;
        }
        int mid = start + (end - start) / 2;
        if (minTree[treeIndex * 2 + 1] <= target) {
            return searchRow(target, maxRow, treeIndex * 2 + 1, start, mid);
        } else if (mid + 1 <= maxRow) {
            return searchRow(target, maxRow, treeIndex * 2 + 2, mid + 1, end);
        } else {
            return -1;
        }
    }
}

[sol1-C#]

public class BookMyShow {
    private int n, m;
    private SegmentTree st;

    public BookMyShow(int n, int m) {
        this.n = n;
        this.m = m;
        this.st = new SegmentTree(n);
    }

    public int[] Gather(int k, int maxRow) {
        int row = st.SearchRow(m - k, maxRow);
        if (row < 0) {
            return new int[0];
        }
        int seats = (int) st.GetSum(row, row);
        st.Add(row, k);
        return new int[]{row, seats};
    }

    public bool Scatter(int k, int maxRow) {
        long remain = (long) (maxRow + 1) * m - st.GetSum(0, maxRow);
        if (remain < k) {
            return false;
        }
        int row = st.SearchRow(m - 1, maxRow);
        while (k > 0) {
            int currRemain = m - (int) st.GetSum(row, row);
            int currSeats = Math.Min(currRemain, k);
            st.Add(row, currSeats);
            k -= currSeats;
            row++;
        }
        return true;
    }
}

class SegmentTree {
    private int n;
    private long[] sumTree;
    private int[] minTree;

    public SegmentTree(int n) {
        this.n = n;
        this.sumTree = new long[n * 4];
        this.minTree = new int[n * 4];
    }

    public long GetSum(int start, int end) {
        return GetSum(start, end, 0, 0, n - 1);
    }

    public void Add(int index, int value) {
        Add(index, value, 0, 0, n - 1);
    }

    public int SearchRow(int target, int maxRow) {
        return SearchRow(target, maxRow, 0, 0, n - 1);
    }

    private long GetSum(int rangeStart, int rangeEnd, int treeIndex, int treeStart, int treeEnd) {
        if (rangeStart == treeStart && rangeEnd == treeEnd) {
            return sumTree[treeIndex];
        }
        int mid = treeStart + (treeEnd - treeStart) / 2;
        if (rangeEnd <= mid) {
            return GetSum(rangeStart, rangeEnd, treeIndex * 2 + 1, treeStart, mid);
        } else if (rangeStart > mid) {
            return GetSum(rangeStart, rangeEnd, treeIndex * 2 + 2, mid + 1, treeEnd);
        } else {
            return GetSum(rangeStart, mid, treeIndex * 2 + 1, treeStart, mid) + GetSum(mid + 1, rangeEnd, treeIndex * 2 + 2, mid + 1, treeEnd);
        }
    }

    private void Add(int rangeIndex, int value, int treeIndex, int start, int end) {
        if (start == end) {
            sumTree[treeIndex] += value;
            minTree[treeIndex] += value;
            return;
        }
        int mid = start + (end - start) / 2;
        if (rangeIndex <= mid) {
            Add(rangeIndex, value, treeIndex * 2 + 1, start, mid);
        } else {
            Add(rangeIndex, value, treeIndex * 2 + 2, mid + 1, end);
        }
        sumTree[treeIndex] = sumTree[treeIndex * 2 + 1] + sumTree[treeIndex * 2 + 2];
        minTree[treeIndex] = Math.Min(minTree[treeIndex * 2 + 1], minTree[treeIndex * 2 + 2]);
    }

    private int SearchRow(int target, int maxRow, int treeIndex, int start, int end) {
        if (minTree[treeIndex] > target) {
            return -1;
        }
        if (start == end) {
            return start;
        }
        int mid = start + (end - start) / 2;
        if (minTree[treeIndex * 2 + 1] <= target) {
            return SearchRow(target, maxRow, treeIndex * 2 + 1, start, mid);
        } else if (mid + 1 <= maxRow) {
            return SearchRow(target, maxRow, treeIndex * 2 + 2, mid + 1, end);
        } else {
            return -1;
        }
    }
}

复杂度分析

• 时间复杂度：构造方法的时间复杂度是 O(n)，方法 gather 的单次时间复杂度是 O(\log n)，方法 scatter 的总体时间复杂度是 O((n + r) \log n)，其中 n 和 m 分别是音乐厅的排数和列数，r 是方法 gather 和 scatter 的调用总次数。
  构造方法创建线段树的时间复杂度是 O(n)。
  每次聚集买票操作需要执行二分查找、线段树计算区间和与线段树更新，因此单次时间复杂度是 O(\log n)。
  每次分散买票操作都会定位到有空座位的最小排数，因此所有分散买票操作对于所有排的遍历总次数是 O(n + r)，每一排的操作时间是 O(\log n)，因此总体时间复杂度是 O((n + r) \log n)。

• 空间复杂度：O(n)，其中 n 是音乐厅的排数。线段树需要 O(n) 的空间。