[LeetCode]Meeting Rooms II

题目链接

首先我们定义一个interval集合的深度d为，当我们用一根竖直的线L从左向右扫的时候，与L相交的intervals的数量的最大值。那么对于这道题，所要用的room的数量n，不可能小于d，因为总有某一时刻有d个meeting同时进行。n也不可能大于d，因为任何一个时刻不可能有大于d个会议同时进行。所以interval集合的深度d，就是这道题的答案，我们也将这道题，转化为求集合深度d的题目。
如何求深度d呢？我们将集合按starting time sort，从左到右遍历，并且把每一个经过的interval的end time放入优先队列，当我们访问某个interval i的时候，将优先队列里比i.start小或等的time pop出，因为这些interval已经不和当前interval相交了，记录此时的深度di，取这些值的最大值就是d。时间复杂度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) {
	int n = intervals.size();
	if(!n)return 0;
	sort(intervals.begin(), intervals.end(), [](const Interval& i1, const Interval& i2){ return i1.start < i2.start; });
	int depth = 1;
	priority_queue<int, vector<int>, greater<int>> ends;
	ends.push(intervals[0].end);
	for(int i = 1; i < intervals.size(); ++i)
	{
	auto interval = intervals[i];
	while(ends.size() && interval.start >= ends.top())
	ends.pop();
	ends.push(interval.end);
	depth = max(depth, static_cast<int>(ends.size()));
	}
	return depth;
	}
	};

view raw Meeting Rooms II.cpp hosted with ❤ by GitHub

领完一种方法就是存event，event分两种，开始和结束。从左向右扫，根据event来更新当前深度即可。时间复杂度O(n * log n)，代码如下：

	/**
	* 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) {
	vector<pair<int, int>> events;
	for(auto& interval : intervals)
	{
	events.push_back({interval.start, 1});
	events.push_back({interval.end, -1});
	}
	sort(events.begin(), events.end());
	int depth = 0, currD = 0;
	for(auto& event : events)
	{
	currD += event.second;
	depth = max(depth, currD);
	}
	return depth;
	}
	};

view raw Meeting Rooms II.cpp hosted with ❤ by GitHub