253. Meeting Rooms II

The idea is to sort the intervals first according to the start time. Then set up a minimum heap according the end time. So when we take the top interval of the heap, we'll get the meeting that ends up earliest. If the new interval starts behind the top meeting, we can reuse the meeting room the top one was using so we don't have to order a new meeting room. All we need to do is to update the end time of this room to eh new interval's end time. Why we don't need to care the gap between the last meeting and the new meeting? Because the intervals are sorted by start time, so it's guaranteed that no new meeting will insert into the gap.

1:  /**  
2:   * Definition for an interval.  
3:   * struct Interval {  
4:   *   int start;  
5:   *   int end;  
6:   *   Interval() : start(0), end(0) {}  
7:   *   Interval(int s, int e) : start(s), end(e) {}  
8:   * };  
9:   */  
10:  struct compare {  
11:    bool operator() (const Interval& a, const Interval& b){  
12:      return a.end > b.end;  
13:    }  
14:  };  
15:  class Solution {  
16:  public:  
17:    int minMeetingRooms(vector<Interval>& intervals) {  
18:      if (intervals.size() == 0) return 0;  
19:      // sort according to the start time.  
20:      sort(intervals.begin(), intervals.end(), [](Interval a, Interval b) { return a.start < b.start; });  
21:      priority_queue<Interval, vector<Interval>, compare> min_heap;  
22:      min_heap.push(intervals[0]);  
23:      for (int i = 1; i < intervals.size(); i++) {  
24:        Interval interval = min_heap.top();  
25:        min_heap.pop();  
26:        if (interval.end > intervals[i].start) {  
27:          min_heap.push(intervals[i]);  
28:        } else {  
29:          interval.end = intervals[i].end;  
30:        }  
31:        min_heap.push(interval);  
32:      }  
33:      return min_heap.size();  
34:    }  
35:  };  

When I revisited this problem, I had a more concise solution with the same idea behind. I don't have to store the intervals in the min heap but the ending time.

1:  /**  
2:   * Definition for an interval.  
3:   * struct Interval {  
4:   *   int start;  
5:   *   int end;  
6:   *   Interval() : start(0), end(0) {}  
7:   *   Interval(int s, int e) : start(s), end(e) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    int minMeetingRooms(vector<Interval>& intervals) {  
13:      if (intervals.size() < 2) return intervals.size();  
14:      sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){ return a.start < b.start; });  
15:      priority_queue<int, vector<int>, greater<int>> q;  
16:      for (int i = 0; i < intervals.size(); i++) {  
17:        if (q.empty() || intervals[i].start < q.top()) q.push(intervals[i].end);  
18:        else {  
19:          int t = q.top();  
20:          q.pop();  
21:          t = intervals[i].end;  
22:          q.push(t);  
23:        }  
24:      }  
25:      return q.size();  
26:    }  
27:  };