Problem Description:

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.

---

The idea is to group those non-overlapping meetings in the same room and then count how many rooms we need. You may refer to .

The code is as follows.

1 class Solution { 2 public: 3     int minMeetingRooms(vector
     
      & intervals) { 4         sort(intervals.begin(), intervals.end(), compare); 5         vector
      
       
        > rooms; 6         int n = intervals.size(); 7         for (int i = 0; i < n; i++) { 8             int idx = findNonOverlapping(rooms, intervals[i]); 9             if (rooms.empty() || idx == -1)10                 rooms.push_back({intervals[i]});11             else rooms[idx].push_back(intervals[i]);12         }13         return (int)rooms.size();14     }15 private:16     static bool compare(Interval& interval1, Interval& interval2) {17         return interval1.start < interval2.start;18     }19     int findNonOverlapping(vector
        
         
          >& rooms, Interval& interval) {20         int n = rooms.size();21         for (int i = 0; i < n; i++)22             if (interval.start >= rooms[i].back().end)23                 return i;24         return -1;25     }26 };
         
        
       
      
     

Update: for each group of non-overlapping intervals, we just need to store the last added one instead of the full list. So we could use a vector<Interval> instead of vector<vector<Interval>> in C++. The code is now as follows.

1 class Solution {  2 public: 3     int minMeetingRooms(vector
     
      & intervals) { 4         sort(intervals.begin(), intervals.end(), compare); 5         vector
      
        rooms; 6         int n = intervals.size(); 7         for (int i = 0; i < n; i++) { 8             int idx = findNonOverlapping(rooms, intervals[i]); 9             if (rooms.empty() || idx == -1)10                 rooms.push_back(intervals[i]);11             else rooms[idx] = intervals[i];12         }13         return (int)rooms.size();14     } 15 private:16     static bool compare(Interval& interval1, Interval& interval2) {17         return interval1.start < interval2.start;18     }19     int findNonOverlapping(vector
       
        & rooms, Interval& interval) {20         int n = rooms.size();21         for (int i = 0; i < n; i++)22             if (interval.start >= rooms[i].end)23                 return i;24         return -1;25     }26 };