Google+ Followers

Monday, August 7, 2017

[Leetcode] Meeting Rooms II, Solution

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.

[Thoughts]
简单的说,把每一个interval铺到时间轴上,统计每个开始点、结束点的room number,然后再做一遍统计,看看在各个时间点上,最大的room number是什么。


[Code]
1:    int minMeetingRooms(vector<Interval>& intervals) {  
2:      map<int, int> deltas;  
3:      for(auto interval : intervals) {  
4:        deltas[interval.start]++;  
5:        deltas[interval.end]--;  
6:      }  
7:        
8:      int max_room = 0, rooms = 0;  
9:      for(auto delta : deltas) {  
10:        rooms += delta.second;  
11:        max_room = max(max_room, rooms);  
12:      }  
13:      return max_room;  
14:    }  
Post a Comment