C++ Solution using Prioruty_queue


  • 0

    /**

    • 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 {
      private:
      static bool Compare(Interval i1, Interval i2){
      if(i1.start == i2.start){
      return i1.end < i2.end;
      }else{
      return i1.start < i2.start;
      }
      }
      public:
      int minMeetingRooms(vector<Interval>& intervals) {
      if(intervals.empty()){
      return 0;
      }
      priority_queue<int, vector<int>, std :: greater<int>> pq;
      sort(intervals.begin(), intervals.end(), Compare);
      int res = 1;
      int empty = 0;
      pq.push(intervals[0].end);
      for(int i = 1; i < intervals.size(); ++i){
      if(intervals[i].start < pq.top()){
      if(empty == 0){
      res++;
      }else{
      empty--;
      }
      pq.push(intervals[i].end);
      }else{
      bool reduce = false;
      while(!pq.empty() && intervals[i].start >= pq.top()){
      if(reduce){
      empty++;
      }
      reduce = true;
      pq.pop();
      }
      pq.push(intervals[i].end);
      }
      }
      return res;
      }
      };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.