Leetcode: Meeting Rooms 2

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] find the minimum number of conference rooms required.

Example

	|---|-----------|
	|-------|-----------|
	|-------| |---| |---|
	|---|---|---|---|---|-----------|
	0---1---2---3---4---5---6---7---8
	vector<vector<int>> tests{{0, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 8}, {1, 3}, {6, 7}, {2, 5}, {4, 5}, {2, 5}, {0, 2}, {1, 2}};

view raw overlaps.txt hosted with ❤ by GitHub

Notice how we need 4 meeting rooms because a maximum number of 4 intervals overlap even though there are more than a total of four overlapping intervals.

Approach

The idea is to count the maximum number of overlapping intervals. First, sort the intervals in order of finishing time. O(n lg n) Second, maintain a min heap of intervals sorted by finishing time (earliest finishing time is at the top). This min heap represents the meeting rooms. Process each interval. At each interval, if the current interval starts after the last interval scheduled finishes, then we can replace that interval with the current interval. Otherwise, we must allocate another room.

	class Solution
	{
	struct _compare
	{
	bool operator()(const vector<int> &lhs, const vector<int> &rhs)
	{
	return lhs[1] > rhs[1];
	}
	} mycompare;
	public:
	int meetings2(vector<vector<int>> meetings)
	{
	// Sort by finish time
	sort(meetings.begin(), meetings.end(),
	[](const vector<int> &lhs, const vector<int> &rhs) {
	return lhs[0] < rhs[0];
	});
	// Order min heap by earliest ending time
	priority_queue<vector<int>, vector<vector<int>>, _compare> pq;
	for (auto &m : meetings)
	{
	if (pq.empty())
	{
	pq.push(m);
	}
	else
	{
	if (m[0] >= pq.top()[1])
	pq.pop();
	pq.push(m);
	}
	}
	return pq.size();
	}
	};

view raw meeting_rooms_ii.cpp hosted with ❤ by GitHub