C++の会議室II

会議の時間間隔の配列があるとします。開始時間と終了時間の2つの時間[[s1、e1]、[s2、e2]、...]があり、各ペアはルール（si

したがって、入力が[[0、30]、[5、10]、[15、20]]の場合、出力は2になります。

これを解決するには、次の手順に従います-

• 1つの優先キューpqを定義する

• 間隔配列を並べ替える

• ret：=0

• 初期化i：=0の場合、i <間隔のサイズの場合、更新（iを1増やします）、実行-

  • while（pqは空ではなく、pqの最上位要素<=interval [i、0]）、do-

    • pqから要素を削除する

  • 間隔[i]をpqに挿入

  • ret：=retの最大値とpqのサイズ

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
struct Comparator{
   bool operator()(vector <int<& a, vector <int<& b){
      return !(a[1] < b[1]);
   }
};
class Solution {
public:
   static bool cmp(vector <int< a, vector <int< b){
      return (a[1] < b[1]);
   }
   int minMeetingRooms(vector<vector<int<>& intervals) {
      priority_queue<vector<int<, vector<vector<int< >, Comparator> pq;
      sort(intervals.begin(), intervals.end());
      int ret = 0;
      for (int i = 0; i < intervals.size(); i++) {
         while (!pq.empty() && pq.top()[1] <= intervals[i][0])
         pq.pop();
         pq.push(intervals[i]);
         ret = max(ret, (int)pq.size());
      }
      return ret;
   }
};
main(){
   vector<vector<int<> v = {{0, 30}, {5, 10}, {15, 20}};
   Solution ob;
   cout << (ob.minMeetingRooms(v));
}

入力

{{0, 30}, {5, 10}, {15, 20}}

出力

2