Leetcode 253 Meeting Room II

题目

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.
Example 1:
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
Example 2:
Input: [[7,10],[2,4]]
Output: 1

解法

解法1：利用最小堆算法

将所有interval的结束时间以最小堆储存，遍历整个interval，每次pop出最早结束的inteval时间，比较当前interval是否与最早结束的interval有重叠，如果有重叠，则无需pop出最早结束的interval，直接加入当前interval，说明需要多加一个room。否则的话，证明room数不需要变化，pop出最早结束的interval，把现在结束的interval push’到最小堆中。最后需要room的长度即为需要的room数

class Solution(object):def minMeetingRooms(self, intervals):""":type intervals: List[List[int]]:rtype: int"""if not intervals:return 0intervals.sort(key=lambda x:x[0])free_rooms = []heapq.heappush(free_rooms,intervals[0][1])for i in intervals[1:]:if free_rooms[0]<=i[0]:heapq.heappop(free_rooms)heapq.heappush(free_rooms,i[1])return len(free_rooms)

C++版本：
两个注意点：

• 利用priority queue作为heap
• 构造compare函数排序

class Solution {
    static bool cmp(const vector<int>& left, const vector<int>& right){
    return left[0] < right[0] || (left[0] == right[0] && left[1] < right[1]);}
public:int minMeetingRooms(vector<vector<int>>& intervals) {
    if (intervals.empty() || intervals[0].empty()) return 0;sort(intervals.begin(),intervals.end(),cmp);priority_queue<int, vector<int>, greater<int>> pq;pq.push(intervals[0][1]);for(int i=1;i<intervals.size();i++){
    if(intervals[i][0]<pq.top()){
    pq.push(intervals[i][1]);}else{
    pq.pop();pq.push(intervals[i][1]);}}return pq.size();};
};

时间复杂度：O(Nlog(N)), 最小堆执行push和pop操作的复杂度为log(N)，需要对N个元素中的所有元素进行一次操作
空间复杂度：O(N), 最坏的情况是需要N个room，那么N个元素都被用来构造最小堆了

解法2：利用扫描线

把所有的interval开始和结束时间进行排序，遍历这个排好序的数组，如果遇到有新会议开始则room数加一，遇到一个会议结束，room数减一，求出整个遍历过程中需要最大的room数便是答案。需要注意的是，当碰到一个一个interval的结束时间和另一个interval的开始时间相等时，需要先减1再加1，因为这种情况下不需要增加room数

class Solution(object):def minMeetingRooms(self, intervals):""":type intervals: List[List[int]]:rtype: int"""if not intervals:return 0tmp = []for i in intervals:tmp.append((i[0],1))tmp.append((i[1],0))tmp.sort(key=lambda x:(x[0],x[1]))curr_max = 0final_max = 0for i in tmp:if i[1]==0:curr_max-=1else:curr_max+=1final_max = max(curr_max,final_max)return final_max

C++版本

class Solution {
    static bool cmp(const vector<int>& left, const vector<int>& right){
    return left[0] < right[0] || (left[0] == right[0] && left[1] < right[1]);}
public:int minMeetingRooms(vector<vector<int>>& intervals) {
    vector<vector<int>> times;for(auto interval : intervals){
    times.push_back({
    interval[0],1});times.push_back({
    interval[1],0});}sort(times.begin(),times.end(),cmp);int count = 0;int ans = 0;for(auto time : times){
    if(time[1] == 0){
    count -= 1;}else{
    count += 1;}ans = max(ans,count);}return ans;}
};

如果vector元素是pair，无需手动定义compare，因为pair会自动比较第一个，然后在比较第二个

class Solution {
    
public:int minMeetingRooms(vector<vector<int>>& intervals) {
    vector<pair<int,int>> times;for(auto interval : intervals){
    times.push_back({
    interval[0],1});times.push_back({
    interval[1],0});}sort(times.begin(),times.end());int count = 0;int ans = 0;for(auto time : times){
    if(time.second == 0){
    count -= 1;}else{
    count += 1;}ans = max(ans,count);}return ans;}
};

时间复杂度和空间复杂度：与解法1相同