首页 > 代码库 > Meeting Rooms II -- LeetCode

Meeting Rooms II -- LeetCode

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.

思路:贪心。

将所有interval按照开始时间从早到晚排序。之后依次安排会议室。当我们考虑一个interval时,查看下当前已经被分配了会议室的时间,如果其中最早的结束时间要早于当前的interval的开始时间,则把该房间分配给当前的interval,否则增加一个会议室。实现时我们可以用最小堆或者优先队列来实现。然后期间会议室数量的最大值就是结果。

时间复杂度为O(NlogN)。

/** * 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 {public:    int minMeetingRooms(vector<Interval>& intervals) {        typedef pair<int, int> interval;        vector<interval> meetings;        for (int i = 0; i < intervals.size(); i++)            meetings.push_back(make_pair(intervals[i].start, intervals[i].end));        sort(meetings.begin(), meetings.end(), less<interval>());        priority_queue<int, vector<int>, greater<int>> q;        int res = 0;        for (int i = 0; i < meetings.size(); i++) {            int end = meetings[i].second;            if (!q.empty() && q.top() <= meetings[i].first) q.pop();            q.push(end);            res = std::max(res, (int)q.size());        }        return res;    }};

 

Meeting Rooms II -- LeetCode