Meeting Rooms II

Problem

Given meeting intervals, find the minimum number of conference rooms required.

Key insight: Sort by start time. Use min-heap of end times. If a room is available (heap top ≤ start), reuse it; else add new room.

Solutions

// C — sort + count overlaps

// C++
int minMeetingRooms(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int>> minH; // end times
    for (auto& iv : intervals) {
        if (!minH.empty() && minH.top() <= iv[0]) minH.pop();
        minH.push(iv[1]);
    }
    return minH.size();
}

// Java
public int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> minH = new PriorityQueue<>();
    for (int[] iv : intervals) {
        if (!minH.isEmpty() && minH.peek() <= iv[0]) minH.poll();
        minH.offer(iv[1]);
    }
    return minH.size();
}

// JavaScript
function minMeetingRooms(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    const ends = [];
    for (const [start, end] of intervals) {
        // find and remove smallest end <= start
        const idx = ends.findIndex(e => e <= start);
        if (idx !== -1) ends.splice(idx, 1);
        ends.push(end);
        ends.sort((a, b) => a - b);
    }
    return ends.length;
}

# Python
import heapq

def minMeetingRooms(intervals):
    intervals.sort()
    heap = []  # end times
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)
        else:
            heapq.heappush(heap, end)
    return len(heap)

Complexity

Time: O(n log n)
Space: O(n)

Key Insight

Heap size = rooms currently in use. When the meeting with the earliest end time ends before our start, we can reuse that room.