1
\$\begingroup\$

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;
};
\$\endgroup\$
  • \$\begingroup\$ Can downvoters please explain the reason why they downvoted this question? \$\endgroup\$ – thadeuszlay Jun 8 at 13:34
  • 3
    \$\begingroup\$ 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? \$\endgroup\$ – Simon Forsberg Jun 8 at 14:17
  • 1
    \$\begingroup\$ Also, your link leads to Leetcode Premium. I mean, not everyone will have a premium account on Leetcode (such as myself). \$\endgroup\$ – Justin Jun 8 at 14:44
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – dfhwze Aug 23 at 6:07
  • \$\begingroup\$ 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. \$\endgroup\$ – thadeuszlay Aug 24 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.