Meeting Rooms II (Min Rooms)

Share

Given an array of meeting time intervals, return 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

Solution Approach

Use separate sorted arrays of start and end times. Two pointers: when next start < current end, we need a new room; otherwise we reuse one.

  • Extract and sort starts[] and ends[] separately.
  • i=0 (start pointer), j=0 (end pointer), rooms=0, maxRooms=0.
  • For each start: if starts[i] < ends[j]: rooms++, i++; else j++, rooms--, i++. Actually: if starts[i]
  • Track max rooms.
Java
import java.util.*;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        int[] starts = new int[n], ends = new int[n];
        for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
        Arrays.sort(starts); Arrays.sort(ends);
        int rooms = 0, maxRooms = 0, j = 0;
        for (int i = 0; i < n; i++) {
            if (starts[i] < ends[j]) rooms++;
            else { rooms--; j++; }
            maxRooms = Math.max(maxRooms, rooms);
        }
        return maxRooms;
    }
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(N)