2406. Divide Intervals Into Minimum Number of Groups
解題說明
Divide Intervals Into Minimum Number of Groups
題目描述：給定一組區間 intervals，其中 intervals[i] = [left, right]。將這些區間分成最少的組數，使得同一組中任意兩個區間不重疊（含端點接觸也算重疊）。回傳最少組數。
解題思路：最少組數等於任意時間點被最多區間同時覆蓋的最大值（「重疊深度」）。
方法：差分陣列（事件掃描）
由於座標範圍最大為 10^6，可使用差分陣列：每個區間 [l, r] 在 l 處 +1、在 r+1 處 -1（注意 +1 因為端點接觸算重疊）。對差分陣列做前綴和，最大值即為答案。
另一等價方法：最小堆 按起點排序，用最小堆記錄每組的終點。對每個新區間，若堆頂（最早結束的組）的終點 < 當前起點（不接觸），可重用該組（更新堆頂）；否則開新組。堆的大小即為組數。
兩種方法答案相同，核心觀察一致：最大重疊數 = 最少組數（區間調色板定理）。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 排序需 O(n log n)，每個區間一次堆入堆出各 O(log n)，整體 O(n log n)。
空間複雜度：O(n) — 最小堆最多同時存放 n 個元素（所有區間互相重疊的極端情況）。
虛擬碼
1. Sort intervals by left endpoint.
2. Initialize min-heap H (stores end times of active groups).
3. For each interval [l, r] in sorted order:
a. If H is not empty and H.top() < l:
- Pop H.top() (reuse that group).
b. Push r into H.
4. Return size of H.其他解法
方法一：差分陣列
建立大小為 max_right+2 的差分陣列，每個區間在 l 加一，在 r+1 減一。前綴和的最大值即為答案。時間 O(n + M)（M 為座標範圍），空間 O(M)。適合座標範圍不大的情況，實作比堆簡單。
方法二：座標壓縮 + 差分 對所有端點做座標壓縮（只處理有事件的點），再做差分掃描。時間 O(n log n)，空間 O(n)，適合座標範圍極大但區間數少的情況。
方法三：雙指針（事件排序） 將所有起點標記為 +1、所有終點+1 標記為 -1，合併排序後線性掃描前綴和，記錄最大值。處理同位置的起點/終點順序需謹慎（終點先於起點可複用）。時間 O(n log n)，空間 O(n)，無需堆。
延伸思考
- 若區間端點接觸（
left == right+1）不算重疊（即開區間），如何修改算法？ - 本題與「會議室 II」（LeetCode 253）幾乎相同，兩題的本質差異在哪裡？
- 若不只求最少組數，還要輸出每個區間對應的組別編號，如何修改算法並保持 O(n log n) 的時間複雜度？