Meeting Rooms II

Share

Given an array of meeting time intervals [start, end], 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

Solution Approach

Sort intervals by start time. Use a min-heap of end times. For each meeting, if earliest-ending room is free, reuse it. Otherwise open a new room.

  • Sort intervals by start time.
  • Min-heap stores end times of occupied rooms.
  • For each interval: if heap.top() <= interval.start, poll (room freed).
  • Push interval.end to heap.
  • Heap size at end = number of rooms needed.
Java
import java.util.*;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int[] interval : intervals) {
            if (!minHeap.isEmpty() && minHeap.peek() <= interval[0])
                minHeap.poll();
            minHeap.offer(interval[1]);
        }
        return minHeap.size();
    }
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(N)