Meeting Rooms II

99.Meeting Rooms II

Heap

Greedy

Sorting

Problem Statement:

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required to schedule all meetings. Overlapping meetings require separate rooms.

Algorithm:

1. Sort the intervals by their start time.
2. Use a min-heap (priority queue) to track the earliest end time of meetings currently using rooms.
3. Iterate through the sorted intervals:
• If the start time of the current meeting is greater than or equal to the earliest end time in the heap, reuse the room by removing the earliest meeting from the heap.
• Otherwise, add the current meeting to the heap.
4. The size of the heap at the end of the iteration represents the minimum number of rooms required.

Complexity:

Time: O(n log n), where n is the number of intervals (sorting + heap operations) | Space: O(n) for the heap.

Java Implementation:

// Heap Solution
public int minMeetingRooms(int[][] intervals) {
    if (intervals == null || intervals.length == 0) return 0;

    // Sort the intervals by start time
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

    // Use a min-heap to track the minimum end time of merged intervals
    PriorityQueue pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

    // Start with the first meeting
    pq.offer(intervals[0]);

    for (int i = 1; i < intervals.length; i++) {
        int[] earliest = pq.peek();

        // If the current meeting starts after the earliest one ends, reuse the room
        if (intervals[i][0] >= earliest[1]) 
            pq.poll();

        // Add the current meeting
        pq.offer(intervals[i]);
    }

    return pq.size(); // Number of rooms required
}
                

Python Implementation:

import heapq

def minMeetingRooms(intervals):
    if not intervals:
        return 0

    # Sort the intervals by start time
    intervals.sort(key=lambda x: x[0])

    # Min-heap to track the minimum end time of merged intervals
    min_heap = []

    # Start with the first meeting
    heapq.heappush(min_heap, intervals[0][1])

    for i in range(1, len(intervals)):
        # If the current meeting starts after the earliest one ends, reuse the room
        if intervals[i][0] >= min_heap[0]:
            heapq.heappop(min_heap)

        # Add the current meeting
        heapq.heappush(min_heap, intervals[i][1])

    return len(min_heap) # Number of rooms required
                

C++ Implementation:

#include 
#include 
#include 
using namespace std;

int minMeetingRooms(vector>& intervals) {
    if (intervals.empty()) return 0;

    // Sort the intervals by start time
    sort(intervals.begin(), intervals.end(), [](const vector& a, const vector& b) {
        return a[0] < b[0];
    });

    // Min-heap to track the minimum end time of merged intervals
    priority_queue, greater> minHeap;

    // Start with the first meeting
    minHeap.push(intervals[0][1]);

    for (int i = 1; i < intervals.size(); i++) {
        // If the current meeting starts after the earliest one ends, reuse the room
        if (intervals[i][0] >= minHeap.top()) 
            minHeap.pop();

        // Add the current meeting
        minHeap.push(intervals[i][1]);
    }

    return minHeap.size(); // Number of rooms required
}