253. Meeting Rooms II

一 開始我想到就是去找最晚關的時間, 跟最早開的時間

然後掃一遍, 看途中最多有幾間會議室開

但這方法會TLE

class Solution {
public:
  
    int minMeetingRooms(vector<vector<int>>& intervals) {
        int start = INT_MAX;
        int end = 0;
        for(int i = 0;i < intervals.size();i++){
            start = min(intervals[i][0], start);
            end = max(intervals[i][1], end);
        }
        int res = 0;
        for(int i = start; i < end; i++){
            int room = 0;
           for(auto m: intervals){
               if(i < m[1] && i >= m[0]){
                   room++;
               }
           }
            res = max(room, res);
        }
        return res;
    }
};

再來我們利用到map再放入會有order的特性

我們就是紀錄開門跟關門的時間, 假設在還沒關門的時候就開門, 就代表同時有兩間會正在開

int minMeetingRooms(vector<vector<int>>& intervals) {
        map<int, int> m;
        for(auto i: intervals){
            m[i[0]]++;
            m[i[1]]--;
        }
        int room = 0;
        int res = 0;
        for(auto i: m){
            room += i.second;
            res = max(room, res);
        }
        return res;
    }
};

另一種方法就是

先將起始時間, 結束時間都整理出來

然後排序, 我們給結束時間一個指針, 然後遍歷起始時間

會發現, 假設起始時間小於結束時間的指針所指的位置, 表示這個時間起始的時候還沒有人結束, 我們便要多開一間, 直到起始時間大於結束時間, 我們才把結束時間的指針往下一個移動, 我覺得沒有上面的方法好理解, 但這方法確實可行

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        vector<int> starts, ends;
          int res = 0;
          int endpos = 0;
          for (auto a : intervals) {
            starts.push_back(a[0]);
            ends.push_back(a[1]);
          }
          sort(starts.begin(), starts.end());
          sort(ends.begin(), ends.end());
          for (int i = 0; i < intervals.size(); i++) {
            if (starts[i] < ends[endpos]) {
              res++;
            } else {
              endpos++;
            }
          }
          return res;
    }
};