# Given time intervals, find the minimum number of conference rooms required

The task is taken from 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.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2


Example 2:

Input: [[7,10],[2,4]]
Output: 1


NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

My solution

/**
* @param {number[][]} intervals
* @return {number}
*/
var minMeetingRooms = function(intervals) {
if (intervals.length <= 1) { return intervals.length; }

const startTimes = [];
const endTimes = [];
intervals.forEach(x => {
startTimes.push(x[0]);
endTimes.push(x[1]);
});
startTimes.sort((a, b) => a - b);
endTimes.sort((a, b) => a - b);

let startPointer = 0;
let endPointer = 0;
let rooms = 0;
while(startPointer < intervals.length) {
if (startTimes[startPointer++] >= endTimes[endPointer]) {
++endPointer;
} else {
++rooms
}
}
return rooms;
};

• Can downvoters please explain the reason why they downvoted this question? – thadeuszlay Jun 8 '19 at 13:34
• I personally did not downvote but I'd recommend taking a look at Simon's Guide to posting a good question. You could improve by providing a description of the approach you are using, for example. Also, why is this called "Meeting Rooms II"? Is it a follow-up to a previous question? – Simon Forsberg Jun 8 '19 at 14:17
• Also, your link leads to Leetcode Premium. I mean, not everyone will have a premium account on Leetcode (such as myself). – Justin Jun 8 '19 at 14:44

## 2 Answers

The code looks much simpler than I would expect for this task. I tried several examples but could neither make it fail, nor did I understand why and how this algorithm works, I was only delighted that it seems to work. Therefore I have only a few remarks.

The early return for length <= 1 is not necessary.

The ++rooms is missing the semicolon.

Apart from that, it looks perfect.

• Whenever a meeting finishes, no new room is required for the next start. Whenever a meeting starts while a meeting is in progress, a new room is required. A meeting is in progress when startTimes[startPointer] < endTimes[endPointer]. The neat trick is that endPointer gets incremented conditionally and that the algorithm does not care about a meeting as start-end, but looks at all meetings as a set of starts and ends. – dfhwze Aug 23 '19 at 6:07
• You sort the startTime and endTime. Then you iterate through every startTime and compare it with the current smallest endTime. If there is a startTime that is less than the current endTime, then you know there is a meeting still going on. Therefore you need a room. If the startTime is equal or greater than the endTime, then you know a meeting has ended and is free and you can use that free room for your current meeting. Therefore no new room is need, instead you look at the next endTime (i.e. increment the endPointer). And so on. You do this until all meetings are checked. – thadeuszlay Aug 24 '19 at 21:55

A solution in C++ could use a min heap to store the end times. This will help clean the code as you could achieve implicit sorting by using min heap.

int solve(vector<vector<int> > &A) {
priority_queue<int,vector<int>,greater<int>> pq;
sort(A.begin(), A.end());
for(auto& i : A){
pq.push(i[1]);
}
int ans = 0;
for(int i = 0 ; i < A.size() ; ++i){
if(!pq.empty() && A[i][0] >= pq.top())
pq.pop();
else
++ans;
}
return ans;
}

• Welcome to the Code Review Community, you could improve your answer by explaining why adding a min heap improves the solution. Code only answers can be down voted and deleted by the community. – pacmaninbw Nov 26 '20 at 13:34
• @RolandIllig This is true. I added the language. – Let us see. Nov 28 '20 at 13:55