What is the core pattern in the 'Booking Concert Tickets in Groups' problem?

The core pattern is binary search over the valid answer space for seat allocation, along with optimization techniques like Binary Indexed Tree and Segment Tree.

How can Binary Indexed Tree help in this problem?

A Binary Indexed Tree allows efficient tracking of seat availability across rows and provides fast updates and queries, making it ideal for seat allocation.

What happens if we don't use binary search or data structures like BIT?

Without binary search or efficient data structures, the solution will become too slow, especially when handling up to 50,000 calls for seat allocation in large halls.

Can we solve the problem without using a Segment Tree?

While a Segment Tree is an optimal choice for range queries, it is possible to solve the problem using other methods, like Binary Indexed Tree or direct binary search over rows.

What are the time and space complexities of this problem?

The time complexity depends on the approach, but it is generally O(log n) for both 'gather' and 'scatter' operations using Binary Search and BIT/Segment Tree. The space complexity is O(n), where n is the number of rows.

#2286

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

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

一个音乐会总共有 n 排座位，编号从 0 到 n - 1 ，每一排有 m 个座椅，编号为 0 到 m - 1 。你需要设计一个买票系统，针对以下情况进行座位安排：同一组的 k 位观众坐在同一排座位，且座位连续。 k 位观众中每一位都有座位坐，但他们不一定坐在一起。由于观众非常挑剔，所…

二分查找设计树状数组线段树

题目描述

一个音乐会总共有 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
                   // 总共只剩下 1 个座位。

提示：

1 <= n <= 5 * 10⁴
1 <= m, k <= 10⁹
0 <= maxRow <= n - 1
gather 和 scatter 总调用次数不超过 5 * 10⁴ 次。

lightbulb

解题思路

方法一：线段树

分析题意我们得知：

对于 gather(k, maxRow) 操作，要求 $k$ 个人坐在同一行并且座位连续，也就是说，我们要找到最小的行，满足该行的剩余座位大于等于 $k$ 。
对于 scatter(k, maxRow) 操作，只需要找到 $k$ 个座位就行，但是要求这 $k$ 个座位的行数尽可能小，因此，我们要找到第一个满足剩余座位数大于 $0$ 的行，进行座位分配，然后继续往后查找。

我们可以用线段树来实现。线段树每个节点的信息有：

l：节点对应的区间左端点
r：节点对应的区间右端点
s：节点对应的区间总的剩余座位数
mx：节点对应的区间最大剩余座位数

注意，线段树节点区间的下标从 $1$ 开始。

线段树的操作有：

build(u, l, r)：建立节点 $u$ ，对应区间 $[l, r]$ ，并递归建立其左右子节点。
modify(u, x, v)：从节点 $u$ 开始，找到对应区间 $[l, r]$ 中的第一个满足 $l = r = x$ 的节点，将该节点的 s 和 mx 修改为 $v$ ，并向上更新。
query_sum(u, l, r)：从节点 $u$ 开始，统计对应区间 $[l, r]$ 中的 s 之和。
query_idx(u, l, r, k)：从节点 $u$ 开始，找到对应区间 $[l, r]$ 中的第一个满足 mx 大于等于 $k$ 的节点，返回该节点的 l。查找时，我们从最大的区间 $[1, maxRow]$ 开始，由于我们要找最左边的满足 mx 大于等于 $k$ 的节点。因此，对于当前区间，我们判断前半部分区间的 mx 是否符合要求，是则说明答案就在前半部分区间，递归查找即可。否则说明答案在后半部分区间，递归查找后半部分区间。
pushup(u)：利用 $u$ 的子节点信息更新当前 $u$ 的信息。

对于 gather(k, maxRow) 操作，我们先用 query_idx(1, 1, n, k) 找到第一个满足剩余座位数大于等于 $k$ 的行，记为 $i$ 。然后我们用 query_sum(1, i, i) 得到该行的剩余座位数，记为 $s$ 。接下来，我们用 modify(1, i, s - k) 将该行的剩余座位数修改为 $s - k$ ，并向上更新。最后，我们返回 $[i - 1, m - s]$ 即可。

对于 scatter(k, maxRow) 操作，我们先用 query_sum(1, 1, maxRow) 统计前 $maxRow$ 行的剩余座位数，记为 $s$ 。如果 $s \lt k$ ，说明没有足够的座位，返回 false；否则，我们用 query_idx(1, 1, maxRow, 1) 找到第一个满足剩余座位数大于等于 $1$ 的行，记为 $i$ 。从该行开始，每次用 query_sum(1, i, i) 得到该行的剩余座位数，记为 $s_i$ 。如果 $s_i \geq k$ ，我们直接用 modify(1, i, s_i - k) 将该行的剩余座位数修改为 $s_i - k$ ，并向上更新，然后返回 true。否则，我们更新 $k = k - s_i$ ，然后将该行的剩余座位数修改为 $0$ ，并向上更新。最后，我们返回 true。

时间复杂度：

初始化的时间复杂度为 $O(n)$ 。
gather(k, maxRow) 的时间复杂度为 $O(\log n)$ 。
scatter(k, maxRow) 的时间复杂度为 $O((n + q) \times \log n)$ 。

整体时间复杂度为 $O(n + q \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $q$ 分别为行数和操作数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

class Node:
    __slots__ = "l", "r", "s", "mx"

    def __init__(self):
        self.l = self.r = 0
        self.s = self.mx = 0


class SegmentTree:
    def __init__(self, n, m):
        self.m = m
        self.tr = [Node() for _ in range(n << 2)]
        self.build(1, 1, n)

    def build(self, u, l, r):
        self.tr[u].l, self.tr[u].r = l, r
        if l == r:
            self.tr[u].s = self.tr[u].mx = self.m
            return
        mid = (l + r) >> 1
        self.build(u << 1, l, mid)
        self.build(u << 1 | 1, mid + 1, r)
        self.pushup(u)

    def modify(self, u, x, v):
        if self.tr[u].l == x and self.tr[u].r == x:
            self.tr[u].s = self.tr[u].mx = v
            return
        mid = (self.tr[u].l + self.tr[u].r) >> 1
        if x <= mid:
            self.modify(u << 1, x, v)
        else:
            self.modify(u << 1 | 1, x, v)
        self.pushup(u)

    def query_sum(self, u, l, r):
        if self.tr[u].l >= l and self.tr[u].r <= r:
            return self.tr[u].s
        mid = (self.tr[u].l + self.tr[u].r) >> 1
        v = 0
        if l <= mid:
            v += self.query_sum(u << 1, l, r)
        if r > mid:
            v += self.query_sum(u << 1 | 1, l, r)
        return v

    def query_idx(self, u, l, r, k):
        if self.tr[u].mx < k:
            return 0
        if self.tr[u].l == self.tr[u].r:
            return self.tr[u].l
        mid = (self.tr[u].l + self.tr[u].r) >> 1
        if self.tr[u << 1].mx >= k:
            return self.query_idx(u << 1, l, r, k)
        if r > mid:
            return self.query_idx(u << 1 | 1, l, r, k)
        return 0

    def pushup(self, u):
        self.tr[u].s = self.tr[u << 1].s + self.tr[u << 1 | 1].s
        self.tr[u].mx = max(self.tr[u << 1].mx, self.tr[u << 1 | 1].mx)


class BookMyShow:
    def __init__(self, n: int, m: int):
        self.n = n
        self.tree = SegmentTree(n, m)

    def gather(self, k: int, maxRow: int) -> List[int]:
        maxRow += 1
        i = self.tree.query_idx(1, 1, maxRow, k)
        if i == 0:
            return []
        s = self.tree.query_sum(1, i, i)
        self.tree.modify(1, i, s - k)
        return [i - 1, self.tree.m - s]

    def scatter(self, k: int, maxRow: int) -> bool:
        maxRow += 1
        if self.tree.query_sum(1, 1, maxRow) < k:
            return False
        i = self.tree.query_idx(1, 1, maxRow, 1)
        for j in range(i, self.n + 1):
            s = self.tree.query_sum(1, j, j)
            if s >= k:
                self.tree.modify(1, j, s - k)
                return True
            k -= s
            self.tree.modify(1, j, 0)
        return True


# Your BookMyShow object will be instantiated and called as such:
# obj = BookMyShow(n, m)
# param_1 = obj.gather(k,maxRow)
# param_2 = obj.scatter(k,maxRow)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Evaluate how well the candidate implements binary search to find seat allocations within rows.
question_mark
Assess whether the candidate effectively utilizes Binary Indexed Tree or Segment Tree for optimization.
question_mark
Check how the candidate handles edge cases, such as when there are very few available seats or when no valid allocation is possible.

warning

常见陷阱

外企场景

error
Forgetting to handle edge cases where no valid seat group can be found within the given rows.
error
Inefficient seat allocation methods that don’t scale well when n and m are large.
error
Not optimizing seat tracking with data structures like Binary Indexed Tree or Segment Tree, leading to excessive computation times.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow partial group reservations where a group can be scattered but still need to sit together in the same row if possible.
arrow_right_alt
Consider adding a feature where groups can reserve seats for future dates, requiring additional optimizations for date management.
arrow_right_alt
Support for dynamic updates to the number of available seats, allowing rows to be added or removed during runtime.

help

常见问题

外企场景

继续练习

#2424 最长上传前缀 #2179 统计数组中好三元组数目 #1157 子数组中占绝大多数的元素