Categories
interview

Meeting Rooms II

Given a list of meetings, that may or may not overlap, calculate the total number of rooms that are required to conduct all the meetings according to the schedule.

Java

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int[] start = new int[intervals.length];
        int[] end = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }

        Arrays.sort(start);
        Arrays.sort(end);

        int endPtr = 0, rooms = 0;
        for (int i = 0; i < intervals.length; i++) {
            if (start[i] < end[endPtr]) {
                rooms++;
            } else {
                endPtr++;
            }
        }
        return rooms;
    }
}

Runtime Complexity: O(nlog(n))

Space Complexity: O(n)

Javascript (ES6)

/**
 * @param {number[][]} intervals
 * @return {number}
 */
const minMeetingRooms = (intervals) => {
  let startList = [];
  let endList = [];
  let endPos = 0;
  let rooms = 0;
  for (let i = 0; i < intervals.length; i++) {
    startList.push(intervals[i][0]);
    endList.push(intervals[i][1]);
  }
  startList.sort((a, b) => a - b);
  endList.sort((a, b) => a - b);
  for (let i = 0; i < intervals.length; i++) {
    if (startList[i] < endList[endPos]) {
      rooms++;
    } else {
      endPos++;
    }
  }
  return rooms;
};

// console.log(minMeetingRooms([[7, 10],[2, 4]]));
// 1

Demo