Meeting Rooms II

Problem

Solution

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var minMeetingRooms = function(intervals) {
  // create separate arrays for start and end
  const start = [];
  const end = [];
  for (const [s, e] of intervals) {
    start.push(s);
    end.push(e);
  }

  // sort start and end
  start.sort((a, b) => a - b);
  end.sort((a, b) => a - b);

  // compute max overlapping intervals
  let rooms = 0;
  let j = 0;
  for (let i = 0; i < start.length; i++) {
    if (start[i] < end[j]) {
      rooms++;
    } else {
      j++;
    }
  }
  return rooms;
};

We will implement a two pointers greedy solution. We can think of this problem as people entering a room at some time and leaving at a different time, with the task of finding the max number of people in said room at the same time. Thus, we first sort the intervals by end and start times. Iterating on start:

• If someone enters before someone else leaves, the max number of people in the room is incremented by 1 (i increments but not j).
• Otherwise, we know someone left before the next person enters, so the two people cancel out (i and j both increments).

This check is performed until there are no more people entering the room.

Another solution is to sort the intervals by start time as well as use a priority queue (min-heap) based on the end time of the intervals. See this for a Java implementation.