HardRating 2470

2286. Booking Concert Tickets in Groups

binary-searchdesignbinary-indexed-treesegment-tree

解題說明

Booking Concert Tickets in Groups

題目描述：設計一個系統來管理音樂會的座位預訂。音樂會有 n 排座位，每排有 m 個座位。你需要實作兩個方法：gather(k, maxRow) 嘗試在第 0 到 maxRow 排中找到連續 k 個座位的同一排，並分配最小編號排的最左邊連續座位；scatter(k, maxRow) 嘗試在第 0 到 maxRow 排中分配 k 個座位（可以跨排），從最小排最左邊的座位開始依序分配。

解題思路：這題需要用線段樹來高效管理每排的剩餘座位數。線段樹的每個節點維護該區間內每排的最大剩餘座位數（用於 gather 快速找到有足夠連續座位的排）以及該區間內所有排的剩餘座位總和（用於 scatter 判斷是否有足夠座位）。

對於 gather(k, maxRow)：在線段樹上查詢 [0, maxRow] 區間中，最大剩餘座位數 >= k 的最小排號，然後分配該排最左邊的 k 個座位。

對於 scatter(k, maxRow)：先檢查 [0, maxRow] 的總剩餘座位是否 >= k，然後從最小排開始逐排分配，直到分配完 k 個座位。

C++ 解法

複雜度分析

時間複雜度：O(n log n) 建構線段樹；gather 為 O(log n)；scatter 最壞情況為 O(n log n)（攤銷為 O(log n)，因每排最多被清空一次）

空間複雜度：O(n) — 線段樹儲存 4n 個節點

虛擬碼

1. Build a segment tree over n rows, each leaf initialized to m (full capacity)
2. Each node stores: max remaining seats in range, sum of remaining seats in range
3. gather(k, maxRow):
   a. Query segment tree for leftmost row in [0, maxRow] with max >= k
   b. If not found, return empty
   c. Calculate seat = m - remaining_seats_in_row
   d. Update that row's remaining seats -= k
   e. Return [row, seat]
4. scatter(k, maxRow):
   a. Query total remaining seats in [0, maxRow]
   b. If total < k, return false
   c. Find first row with seats >= 1
   d. Greedily fill rows from left: take min(remain, row_seats) from each row
   e. Return true

其他解法

分塊（Sqrt Decomposition）法：將 n 排分成 sqrt(n) 塊，每塊維護最大值和總和。時間複雜度 O(sqrt(n))，實作較簡單但常數較大。
BIT（樹狀陣列）法：用兩個樹狀陣列分別維護總和。但 gather 操作需要找最大值位置，BIT 不太適合範圍最大值查詢，需要額外的二分搜尋，實作複雜度較高。

延伸思考

如果需要支援「取消預訂」操作（釋放特定排的特定座位），資料結構需要如何修改？
如果座位有不同的票價，且 gather 需要返回票價最低的連續座位，如何調整演算法？
如果有多個音樂會同時售票（多個獨立的座位系統），如何設計高效的並行方案？

解題說明

Booking Concert Tickets in Groups

對於 gather(k, maxRow)：在線段樹上查詢 [0, maxRow] 區間中，最大剩餘座位數 >= k 的最小排號，然後分配該排最左邊的 k 個座位。

對於 scatter(k, maxRow)：先檢查 [0, maxRow] 的總剩餘座位是否 >= k，然後從最小排開始逐排分配，直到分配完 k 個座位。

虛擬碼

1. Build a segment tree over n rows, each leaf initialized to m (full capacity) 2. Each node stores: max remaining seats in range, sum of remaining seats in range 3. gather(k, maxRow): a. Query segment tree for leftmost row in [0, maxRow] with max >= k b. If not found, return empty c. Calculate seat = m - remaining_seats_in_row d. Update that row's remaining seats -= k e. Return [row, seat] 4. scatter(k, maxRow): a. Query total remaining seats in [0, maxRow] b. If total < k, return false c. Find first row with seats >= 1 d. Greedily fill rows from left: take min(remain, row_seats) from each row e. Return true

其他解法

分塊（Sqrt Decomposition）法：將 n 排分成 sqrt(n) 塊，每塊維護最大值和總和。時間複雜度 O(sqrt(n))，實作較簡單但常數較大。
BIT（樹狀陣列）法：用兩個樹狀陣列分別維護總和。但 gather 操作需要找最大值位置，BIT 不太適合範圍最大值查詢，需要額外的二分搜尋，實作複雜度較高。

延伸思考

如果需要支援「取消預訂」操作（釋放特定排的特定座位），資料結構需要如何修改？
如果座位有不同的票價，且 gather 需要返回票價最低的連續座位，如何調整演算法？
如果有多個音樂會同時售票（多個獨立的座位系統），如何設計高效的並行方案？