題目網址：https://leetcode.cn/problems/meeting-rooms-ii/

題意：給一 array intervals, 其中 intervals[i] = [start_i, end_i], 返回所需的最小會議室數量。

注意：(0, 8) 和 (8, 10) 並不衝突

Solution 1：

想法：利用 heap 來紀錄所有會議室的 end, 並每次取 heap 中最小的, 來確認跟當前 interval 是否有衝突

  • 若有, 則將當前 interval.end 加入到 heap 中
  • 若沒有, 則把 top 取代為當前 interval.end（先 pop(), 再 push(newEnd)）
class Solution {
public:
    int minMeetingRooms(vector<Interval> &intervals) {
        int res = 1;
        priority_queue<int, vector<int>, greater<>> pq; // min heap

        sort(intervals.begin(), intervals.end(), [](const Interval& i1, const Interval& i2) {
            return i1.start < i2.start;
        });

        pq.emplace(intervals[0].end);
        for (int i = 1; i < intervals.size(); ++i) {
            const auto minEnd = pq.top();

            // 有重疊, 要加開會議室
            if (minEnd > intervals[i].start) {
                ++res;
            } else { // 沒重疊
                pq.pop();
            }

            pq.emplace(intervals[i].end);
        }

        return res;
    }
};
  • time：$O(n \cdot log(n))$
    • $O(n \cdot log(n))$ : sorting
    • $O(n \cdot log(n))$ : n 次從 minHeap 中取 top, 每次取完後會調整 heap, 需 $O(log(n))$
  • space：$O(n)$ ➔ heap size 最大為 n 個

Solution 2：

想法：占用資源問題可看做是上下車問題, 則問題可轉化成車上最多有幾人

e.g. intervals = [[0,30], [5,10], [15,20]]

可想成：

  • 第一個人從 0 上車, 從 30 下車
  • 第二個人從 5 上車, 從 10 下車
  • 第三個人從 15 上車, 從 20 下車

問題可轉化成車上最多有幾人（最多有幾間會議室）

顯然：上車, 車上人數+1；下車, 車上人數-1

先把 intervals 拆解成：

上車 : [0, 1], [5, 1], [15, 1]
下車 : [10, -1], [20, -1], [30, -1]
時間 0 5 10 15 20 30
變化 +1 +1 -1 +1 -1 -1
人數 1 2 1 2 1 0

➔ 車上最多 2 人

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        const int n = intervals.size();
        vector<pair<int, int>> meetings;

        for (const auto& iv : intervals) {
            meetings.emplace_back(iv[0], 1); // 上車, cnt + 1
            meetings.emplace_back(iv[1], -1); // 下車, cnt - 1
        }

        sort(meetings.begin(), meetings.end());

        int cnt = 0, maxVal = 0;
        for (const auto& m : meetings) {
            cnt += m.second;
            maxVal = max(maxVal, cnt);
        }

        return maxVal;
    }
};
  • time：$O(n \cdot log(n))$ ➔ sorting
  • space：$O(n)$ ➔ meetings