🔗 🟡 2406. Divide Intervals Into Minimum Number of Groups 1713

tags: `WeeKly Contest 310` `貪心(Greedy)` `排序(Sorting)` `堆積(Heap)`

題意

給定一個二維整數陣列 $intervals$ ，其中 $intervals[i] = [left_i, right_i]$ 代表包含區間 $[left_i, right_i]$ 。

你需要將這些區間分成一個或多個小組，使得每個區間恰好屬於一個小組，且同一小組內的任意兩個區間 不相交。

請返回你所需要的最少小組數。

如果兩個區間有至少一個共同數字，則稱它們相交。例如，區間 $[1, 5]$ 和 $[5, 8]$ 相交。

約束條件

$1 \leq \text{intervals.length} \leq 10^5$
$\text{intervals[i].length} = 2$
$1 \leq \text{left}_i \leq \text{right}_i \leq 10^6$

思路：貪心(Greedy) + 堆積(Heap)

這題是經典的 Interval Partitioning 問題，可以透過貪心(Greedy) + 堆積(Heap) 來解決。

首先可以思考，在已經有一些小組的情況下，如何判斷一個新的區間可以加入到哪一個小組中？

如果某個小組的結束時間小於新的區間的開始時間，說明我們可以將新的區間加入到這個小組中；若所有小組的結束時間都大於新的區間的開始時間，說明我們需要創建一個新的小組。
而在這些已經有的小組中，使用最早結束的那一個小組是最優的，這是因為若我們可以確保在未分組的區間中，沒有比當前區間的開始時間更早的區間，那麼我們可以基於貪心(Greedy) 思路，將當前區間加入到最早結束的小組中，這樣可以留出最多的空間給後續的區間使用。
此外，若最早結束的小組時間大於當前區間的開始時間，說明所有小組的結束時間都大於當前區間的開始時間，我們需要創建一個新的小組。

為了確保在未分組的區間中，沒有比當前區間的開始時間更早的區間，我們可以先依照區間的開始時間進行排序(Sorting) ，並在遍歷每個區間時，只需要檢查最早結束的小組時間即可，這可以透過維護一個最小堆積(Min Heap) 來實現。

而在遍歷完成後，堆積的大小就是我們所需要的最少小組數，直接返回堆積的大小即可。

具體步驟如下：

將所有區間按照開始時間進行排序。
使用最小堆來維護每個小組的結束時間。
遍歷每個區間，對於每個區間，我們有兩種可能的操作：
- 如果堆不為空，且堆頂元素（最早的結束時間）小於當前區間的開始時間，說明我們可以將當前區間加入到一個已存在的小組中。我們移除堆頂元素，並將當前區間的結束時間加入堆中，相當於更新該小組的結束時間。
- 否則，我們需要創建一個新的小組，並將當前區間的結束時間加入堆中。
最後，堆積的大小就是我們所需要的最少小組數。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ $O (n lo g n)$ ，其中 $n$ $n$ 是區間的數量。
- 排序的時間複雜度為 $\mathcal{O}(n \log n)$ ；
- 遍歷區間的時間複雜度為 $\mathcal{O}(n)$ ；
- 每次操作堆的時間複雜度為 $\mathcal{O}(\log n)$ ，總共需要操作 $\mathcal{O}(n)$ 次。
空間複雜度： $\mathcal{O}(n)$ $O (n)$ 。
- 使用了一個堆來維護每個小組的結束時間，最壞情況下需要存儲所有區間的結束時間。

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda x : x[0])
        hp = []
        for left, right in intervals:
            if hp and left > hp[0]:
                heappop(hp)
            heappush(hp, right)
        return len(hp)

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        });
        priority_queue<int, vector<int>, greater<int>> hp; // Min Heap
        for (const auto& interval : intervals) {
            if (!hp.empty() && hp.top() < interval[0]) {
                hp.pop();
            }
            hp.push(interval[1]);
        }
        return hp.size();
    }
};