# 253 - Meeting Rooms II

解法一 - Merge Interval（Failed）

一開始的想法很單純，想說可以用 Merge interval 的方式，maintain 一個 vector，最新的 interval 只要跟 vector 的最後比較就好，實作如下：

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        // Sort the intervals
        sort(intervals.begin(), intervals.end(), 
             [](vector<int>& a, vector<int>& b) {
                 return a[0] < b[0];
        });

        // Start checking
        int minRoom = 0;

        vector< vector<int> > cur;
        for(auto& interval: intervals) {
            if(cur.empty()) {
                cur.push_back(interval);
            }
            else{
                while(!cur.empty() and cur.back()[1] <= interval[0]) {
                    cur.pop_back();
                }
                cur.push_back(interval);
            }

            minRoom = max(minRoom, (int)cur.size());
        }

        return minRoom;
    }
};

但這個實作會掛在這種 case：

[[9,10],[4,9],[4,17]]

sort 完畢會是：

[[4,9],[4,17],[9,10]]

因為 9 比 17 小，所以我們會同時把 [4,9]、[4,17]、[9,10] 放進 cur 裡面，於是就以為需要三間 room。不過這個解法也已經能處理掉五十幾個 case，值得紀錄一下提醒自己這樣想會錯。

解法二 - Min Heap 記錄最早結束的 meeting

這篇把解法的思路寫得非常清晰：

實作如下：

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if(intervals.empty()) {
            return 0;
        }

        // Sort the intervals
        sort(intervals.begin(), intervals.end(), 
             [](const vector<int>& a, const vector<int>& b) {
                 return a[0] < b[0];
        });

        // Start checking
        priority_queue<int, vector<int>, greater<int>> cur;
        cur.push(intervals[0][1]);
        int minRoom = 1;

        for(int i = 1; i < intervals.size(); ++i) {
            while(!cur.empty() and cur.top() <= intervals[i][0]) {
                cur.pop();
            }

            cur.push(intervals[i][1]);

            minRoom = max(minRoom, (int)cur.size());
        }

        return minRoom;
    }
};