[leetcode] 253. Meeting Rooms II 解題報告

題目連結：https://leetcode.com/problems/meeting-rooms-ii/

Given an array of meeting time intervals consisting of start and end times 

[[s1,e1],[s2,e2],...]

 (si < ei), find the minimum number of conference rooms required.

For example,

Given 

[[0, 30],[5, 10],[15, 20]]

,

return 

2

.

思路：可以按照每個區間的起點排序, 然後依次将每個區間的終點放到一個集合中,如果下一個區間起點大于等于之前某區間的終點, 就将其從集合中删除. 這種做法的原理是如果一個區間的起點大于等于另一個區間的終點, 那麼他們是不重合的.

代碼如下:

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) {
        auto cmp = [](Interval a, Interval b) { return a.start<b.start;};
        sort(intervals.begin(), intervals.end(), cmp);
        multiset<int> st;
        int Max = 0;
        for(auto val: intervals)
        {
            while(!st.empty()&&val.start>= *st.begin()) st.erase(st.begin());
            st.insert(val.end);
            Max = max(Max, (int)st.size());
        }
        return Max;
    }
};
           

還有另一個比較簡潔的方法. 每個區間的起始點代表一個區間的開始，會将重疊區域＋１，每個區間的結束點代表一個區間的結束，将會使重疊區域－１，是以我們可以利用這個性質，并結合STL的map來實作

代碼如下：

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) {
        map<int, int> hash;
        for(auto val: intervals)
            hash[val.start]++, hash[val.end]--;
        int ans = 0, sum = 0;
        for(auto val: hash)
            sum += val.second, ans = max(ans, sum);
        return ans;
    }
};
           

參考：https://leetcode.com/discuss/58720/c-solution-using-a-map-total-11-lines